Solving Single Machine Bi-Criteria and Bi-Objectives Scheduling Problems of Total Tardiness and Range of Lateness Using Exact and Local Search Methods

Abstract

In manufacturing and production planning environments, where efficiency depends on optimizing time-based performance measures, scheduling operations on a single machine is a foundational challenge. This study examines a single-machine scheduling problem (MSP) focusing on minimizing the total tardiness of jobs and the range of late jobs as evaluation criteria. The problem is formulated in two ways: a bi-criteria model  and a bi-objective model  each of them is NP-hard problem. In theoretical part: Several special cases of these formulations are analyzed to better understand their characteristics. Some cases were provided that lead to the optimal solution, and others led to efficient solutions. While in practical part: To obtain effective solutions, local search methods such as the Artificial Bee Colony algorithm and Tabu Search are proposed and applied. In addition, some exact and modified solution techniques are used to solve the problems and verify the obtained results. Computational experiments demonstrate the efficiency and accuracy of the proposed approaches in solving both scheduling models.