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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Biskup D (1999). Single machine scheduling with learning considerations. European Journal of Operational Research 115 (1): 173–178.
Burkard R, Dell’Amico M and Martello S (2012). Assignment Problems. Society of Industrial and Applied Mathematics: Philadelphia.
Che A and Chu C (2009). Multi-degree cyclic scheduling of a no-wait robotic cell with multiple robots. European Journal of Operational Research 199 (1): 77–88.
Gawiejnowicz S (2008). Time-dependent Scheduling. Springer: Berlin.
Hall NG and Sriskandarajah CA (1996). A survey of machine scheduling problems with blocking and no-wait in process. Operations Research 44 (3): 510–525.
Karzanov AV and Livshits EM (1978). Minimal quantity of operators for serving a homogeneous linear technological process. Automation and Remote Control 39 (3): 445–450.
Kats V and Levner E (2002). Cyclic scheduling in a robotic production line. Journal of Scheduling 5 (1): 23–41.
Leung J and Levner E (2006). An efficient algorithm for multi-hoist cyclic scheduling with fixed processing times. Operation Research Letters 34 (4): 465–472.
Mosheiov G (2001a). Scheduling problems with learning effect. European Journal of Operational Research 132 (3): 687–693.
Mosheiov G (2001b). Parallel machine scheduling with learning effect. Journal of the Operational Research Society 52 (10): 1165–1169.
Mosheiov G and Sidney JB (2003). Note on scheduling with general learning curves to minimize the number of tardy jobs. European Journal of Operational Research 147 (3): 665–670.
Mosheiov G and Sidney JB (2005). A note on scheduling with learning effect to minimize the number of tardy jobs. Journal of the Operational Research Society 56 (1): 110–112.
Shabtay D, Arviv K, Stern H and Eday Y (2014). A combined robot selection and scheduling problem for flow-shops with no wait restrictions. Omega 43: 96–107.
Wright TP (1936). Factors affecting the cost of airplanes. Journal of the Aeronautical Sciences 3 (4): 122–128.
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.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Oron, D. No-wait scheduling of position dependent jobs and adjustable processing intervals. J Oper Res Soc 66, 732–736 (2015). https://doi.org/10.1057/jors.2014.54
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2014.54