Minimizing the total earliness and tardiness for single machine scheduling problems with restricted due date and sequence-dependent setup times

viMINIMIZING THE TOTAL EARLINESS AND TARDINESS FOR SINGLEMACHINE SCHEDULING PROBLEMS WITH RESTRICTED DUE DATEAND SEQUENCE-DEPENDENT SETUP TIMES(M.Sc. Thesis)Müge Hanım ÖZDEM RGAZ UNIVERSITYINSTITUTE OF SCIENCE AND TECHNOLOGYJanuary 2007ABSTRACTIn this thesis, a single-machine scheduling problem including sequence-dependent setup times is discussed. All jobs have a common due date in thisproblem and it is not desired that the jobs complete before or after the due date.In the literature, this problem is known as the Earliness/Tardiness (E/T)problem. The main objective is minimizing the total amount of earliness andtardiness. The E/T problem became common by the popularity of the Just-In-Time (JIT) Japanese manufacturing philosophy increased.In this research, earliness and tardiness have equal weights and the due date iscommon and restricted for all jobs. In the most scheduling literature, machinesetup time was ignored or assumed to be part of the jobs? processing times. Inthis thesis, the machine setup is separated from the processing time and isconsidered to be sequence-dependent. The intricacy of the problem increasesdramatically and the problem becomes NP-hard when sequence-dependentsetup times are included. Therefore, optimal solutions cannot be obtained in apolynomial time.A Mixed Integer Programming (MIP) is used to obtain optimal solutions forsmall sized problems. For large-sized problems, obtaining optimal solutionsusing exact methods is not feasible. Therefore, the ?Shortest AdjustedviiProcessing Time First? (SAPT) heuristic developed before for unrestrictedcommon due date of this problem is also adapted to restricted version. After, aTabu Search (TS) algorithm is implemented to find better solutions using thebest solution of the SAPT heuristic as an initial solution. The performance of theSAPT heuristic and the TS algorithm are measured by considering thedeviations of their solutions from the optimal solutions. SAPT heuristic providedacceptable solutions; however, the TS algorithm outperformed the SAPTheuristic in the most cases and results for problems up to 180 jobs were found.Science Code : 906.1.141Key Words : Earliness, tardiness, sequence-dependent, restricted, singlemachinePage Number : 109Adviser : Assoc. Prof. Ertan GÜNER