A GREEDY HEURISTIC FOR BICRITERION SINGLE-MACHINE SCHEDULING PROBLEMS

This paper presents a greedy heuristic for solving a bicriterion single machine scheduling problem. The job to be scheduled on the machine has an available time, a(i), a processing time, p(i), a system time, q(i) and a due date, d(i). With the makespan as a performance measure, Schrage has presented a heuristic approach by choosing the ready job with the largest tail to solve the problem. Moreover, Carlier has further improved this heuristic and provided an efficient branch and bound procedure with successful runs of thousand jobs reported. In this research, we introduce the total absolute deviation as another criterion to be considered for the cell coordination purpose. As a result, a bicriterion single machine scheduling problem is formed and the bicriterion includes the minimization of the makespan and the total absolute deviation. The absolute deviation of each job is a non-regular performance measure and is defined as the absolute difference between the job's system completion time (i.e. including q(i)) and its due date. We have assumed a linear combination of these two objectives and present a greedy heuristic which uses the control parameter alpha to manipulate a(i) and q(i) of each job to generate a set of nondominant schedules for satisfying these two performance measures. According to this set of schedules, shop floor managers can make a decision based on their application purposes.