No-wait scheduling of position dependent jobs and adjustable processing intervals

Abstract

In this paper, we consider a single machine no-wait scheduling model whereby job processing times are general functions of their position in the job sequence. We assume that the single machine must operate at a certain cycle, which can be determined by the scheduler. Furthermore, exactly one job has to be completed by the end of each cycle. Using different variations of the Linear Assignment Problem formulation, we develop polynomial time algorithms for minimizing the following objectives: makespan, total completion time, maximum earliness and total earliness.

Keywords:

• no-wait scheduling
• makespan
• total completion time
• earliness
• total earliness
• processing interval

Acknowledgements

The author is grateful to the Associate Editor and the anonymous reviewers for their valuable feedback and helpful suggestions. The author would also like to thank Clara Coifman and Benjamin Ostroviecki for the insightful conversations on the model studied in this article.