A bi-criteria algorithm for the simultaneous minimization of makespan and number of tardy jobs on a single machine with sequence dependent set-up time

Abstract

Scheduling models based on efficient resources utilization without sufficient consideration for customer satisfaction or vice-visa is inadequate in many real-life multi-criteria scheduling problems. This work was aimed at the development of a bi-criteria algorithm for the simultaneous optimization of Makespan (Cmax) and Number of tardy jobs (NT) in a single machine problem with Sequence dependent set-up time. An existing single criterion algorithm, the Set Sequencing Algorithm, was adapted to solve the bi-criteria problem, Graphical User Interface (GUI) based software of the new algorithm was developed and its performance was evaluated with a real life problem and 150 randomly generated problems, with problem sizes ranging from between 20 and 150. The values of Crnax and NT of the solution sequences were analysed. The output sequences gave an average reduction of 32.1 0% in both measures of performance compared with the input sequences. The software was also shown to be user friendly. It is concluded that Set sequencing Algorithm is suitable for bi criteria scheduling optimization