Article ID: | iaor2003950 |
Country: | United Kingdom |
Volume: | 53 |
Issue: | 6 |
Start Page Number: | 688 |
End Page Number: | 693 |
Publication Date: | Jun 2002 |
Journal: | Journal of the Operational Research Society |
Authors: | Cheng T.C. Edwin, Ng C.T., Janiak A., Bachman A. |
This paper deals with a single machine scheduling problem with start time dependent job processing times. The job processing times are characterized by decreasing linear functions dependent on their start times. The problem is to find a schedule for which the total weighted completion time is minimized. It is proved that the problem is NP-hard. Some properties of special cases of the general problem are also given. Based on these results, two heuristic algorithms are constructed and their performance is compared.