Common due-date assignment and scheduling on a single machine with sequence-dependent setups and discretely controllable job processing times

Abstract

This thesis considers single machine common due-date assignment and scheduling with controllable processing times, which is the problem of determining the common due-date, the processing times and the sequence of jobs to be processed on a single machine. The controllable processing times of each job is considered in the discrete form in that it is determined by selecting one of its discretely available processing times. Moreover, the sequence-dependent setup, in which setup times depend on the type of job just completed and job to be processed, is considered. A mixed integer programming model is proposed for the problem with the objective of minimizing the sum of earliness, tardiness, due-date assignment and job processing costs, where the job processing costs may be different for different available processing times. Then, due to the complexity of the problem, the two-stage heuristic algorithms are proposed in which an initial solution is obtained according to the positional weights and then it is improved by various interchange methods together with determining the job processing times. Computational experiments were done on various randomly generated test instances and the results are reported.