Single Machine Scheduling and Due Date Assignment with Past-Sequence-Dependent Delivery Times and Position-Dependent Processing Times

Abstract:

This paper considers single machine scheduling and due date assignment problems in which the jobs need to be delivered to customers after processing. It is assumed that the delivery times are proportional to the length of the already processed jobs, and a job's processing time depends on its position in a sequence. The objective functions include total earliness, the weighted number of tardy jobs and the cost of due date assignment. We analyze the problems with two different due date assignment methods and conclude that the problems are polynomial time solvable. We provide a dynamic programming algorithm with O(n³) times for the problems.

• Periodical: Advanced Materials Research (Volumes 1006-1007)
• Pages: 498-503
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.1006-1007.498
• Online since: August 2014
• Authors: Yu Fang Zhao
• Keywords: Delivery Time, Due Date Assignment, Position-Dependent Processing Times, Scheduling, Single Machine

References

[1] A. Bachman and A. Janiak: Scheduling Jobs with Position-dependent Processing Times. Journal of the Operational Research Society, Vol. 55 (2004) , 257-264.

DOI: 10.1057/palgrave.jors.2601689

[2] D. Biskup: Single-machine Scheduling with Learning Considerations. European Journal of Operational Research, Vol. 115 (1999), 173-178.

DOI: 10.1016/s0377-2217(98)00246-x

[3] D. Biskup: A State-of-the-art Review on Scheduling with Learning Effects. European Journal of Operational Research, Vol. 188 (2008) 315-329.

DOI: 10.1016/j.ejor.2007.05.040

[4] G. Mosheiov: Parallel Machine Scheduling with a Learning Effect. Journal of Operational Research Society, Vol. 52 (2001) 1165-1169.

DOI: 10.1057/palgrave.jors.2601215

[5] A. Janiak and R. Rudek: Scheduling Jobs Under an Aging Effect. Journal of the Operational Research Society, Vol. 60 (2009)1-8.

[6] K. Rustogi and V.A. Strusevich: Simple Matching vs Linear Assignment in Scheduling Models with Positional Effects: A Critical Review. European Journal of Operational Research, Vol. 222(2012)393-407.

DOI: 10.1016/j.ejor.2012.04.037

[7] G. Mosheiov: Proportionate flow shops with general position-dependent processing times. Information Processing Letters, Vol. 111 (2011) 174-117.

DOI: 10.1016/j.ipl.2010.11.016

[8] C.L. Zhao Y.Q. Yin, T.C.E. Cheng and C.C. Wu: Single machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial and Management Optimization, Vol. 10 (2014) 691-700.

[9] K. Rustogi and V. A Strusevich: Simple Matching vs Linear Assignment in Scheduling Models with Positional Effects: A Critical Review. European Journal of Operational Research, Vol. 222 (2012)393-407.

DOI: 10.1016/j.ejor.2012.04.037

[10] C. Koulamas and G.J. Kyparisis: Single-machine Scheduling Problems with Past-sequence -dependent Delivery Times, International Journal of Production Economics, Vol. 126 (2010) 264–266.

DOI: 10.1016/j.ijpe.2010.03.016

[11] Y.Q. Yin, M. Liu, T.C.E. Cheng, C.C. Wu and S.R. Cheng: Four single-machine scheduling problems involving due date determination decisions. Information Sciences, Vol. 251 (2013) 164-181.

DOI: 10.1016/j.ins.2013.06.035

[12] G. H. Hardy, J. E. Littlewood, and G. Polya. 1967. Inequalities. London: Cambridge University Press.