Minimizing cycle time in single machine scheduling with start time-dependent processing times

作者：Farahani Mehdi Hosseinabadi^*; Hosseini Leila

来源：International Journal of Advanced Manufacturing Technology, 2013, 64(9-12): 1479-1486.

DOI：10.1007/s00170-012-4116-1

• Scheduling
• Single machine
• Time-dependent processing times
• Cycle time

This paper considers the single machine scheduling problem with a new version of time-dependent processing times. The processing time of a job is defined as a piecewise linear function of its start time. It is preferred that the processing of each job be started at a specific time which means that processing the job before or after that time implies additional effort to accomplish the job. The job-processing time is a nonmonotonic function of its start time. The increasing rate of processing times is job independent and the objective is to minimize the cycle time. We show that the optimal schedule is V shaped and propose an optimal polynomial time algorithm for the problem.

• 出版日期2013-2