Article ID: | iaor19951330 |
Country: | United Kingdom |
Volume: | 22 |
Issue: | 2 |
Start Page Number: | 205 |
End Page Number: | 219 |
Publication Date: | Feb 1995 |
Journal: | Computers and Operations Research |
Authors: | Cheng T.C.E., Li Chung-Lun, Chen Z.-L. |
Keywords: | heuristics |
The authors consider a single-machine scheduling problem in which every job has a given target start time and a due-date. A job is early if processing commences before its start time and is tardy if it is completed after its due-date. The objective is to minimize the weighted number of early and tardy jobs, with the restriction that the start times and due-dates are ‘agreeable’, i.e., the start times must increase in the same sequence as the due-dates. The authors show that the problem is NP-complete in the strong sense. The complexity issues and algorithms for some special cases of this problem are discussed, and heuristic algorithms are developed for the general problem. Computational experiments are conducted to show the effectiveness of the heuristics.