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.
- Computational analysis
- Single machine
- Start time dependent processing time
ASJC Scopus subject areas
- Management of Technology and Innovation
- Strategy and Management
- Management Science and Operations Research