Solving Bicriteria Total Tardiness Times and Maximum Tardiness Machine Scheduling Problems

Abstract

This research addresses the Single Machine Scheduling Problem (MSP) under two performance criteria: maximum tardiness and total tardiness . Given that this problem is classified as NP-hard, the study focuses on developing efficient solution methodologies that balance solution quality with computational efficiency. The MSP is mathematically formulated through two models: a bi-criteria MSP (BCMSP) and bi-objectives (BOMSP) based on minimizing the Euclidean distance. The theoretical framework involves deriving, dominance rules (DR) and analytical results for specific cases, enabling efficient (optimal) solutions to be identified directly under certain conditions. On the practical side, exact solution techniques were developed using the Branch and Bound (BAB) method. Furthermore, two heuristic algorithms (HA's), were proposed to handle large-scale instances. Experimental results, involving instances with up to more than 4000 jobs, demonstrate that the proposed algorithms can find efficient solutions within reasonable computational times.