Scheduling start time dependent jobs to minimize the total weighted completion time |
| |
Authors: | A Bachman T C E Cheng A Janiak C T Ng |
| |
Institution: | 1.Wroclaw University of Technology,Wroclaw,Poland;2.The Hong Kong Polytechnic University,Hong Kong |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |