Single-machine scheduling and due date assignment with rejection andposition-dependent processing times

Chuanli Zhao; Yunqiang Yin; T. C. E. Cheng; Chin-Chia Wu

doi:10.3934/jimo.2014.10.691

Article Contents

2014, Volume 10, Issue 3: 691-700. Doi: 10.3934/jimo.2014.10.691

This issue Previous Article Humanitarian logistics planning for natural disaster response with Bayesian information updates Next Article Cyber-physical logistics system-based vehicle routing optimization

Single-machine scheduling and due date assignment with rejection and position-dependent processing times

1.
School of Mathematics and Systems Science, Shenyang Normal University, Shenyang, Liaoning, 110034
2.
State Key Laboratory Breeding Base of Nuclear Resources and Environment, East China Institute of Technology, Nanchang, Jiangxi 330013
3.
Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong
4.
Department of Statistics, Feng Chia University, Taichung

Received: April 2013

Revised: June 2013

Published: July 2014

Abstract Related Papers Cited by

Abstract

This paper considers a single-machine scheduling and due date assignment problem in which the processing time of a job depends on its position in a processing sequence and jobs can be rejected by incurring penalties. The objective is to minimize the sum of the scheduling criterion of the accepted jobs and the total penalty of the rejected jobs. We first consider the problem with the common due date assignment method where the scheduling criterion is a cost function that includes the costs of earliness, tardiness, and due date assignment. We provide a polynomial-time algorithm to solve the problem. We then provide a unified model for solving the single-machine scheduling problem with rejection and position-dependent processing times. Finally, we extend the results to the setting involving various due date assignment methods.

Keywords:

Mathematics Subject Classification: Primary: 90B35; Secondary: 90C26.

Citation:

Related Papers

Cited by

References

[1]	G. I. Adamopoulos and C. P. Pappis, Single machine scheduling with flow allowances, Journal of the Operational Research Society, 47 (1996), 1280-1285.
[2]	A. Bachman and A. Janiak, Scheduling jobs with position-dependent processing times, Journal of the Operational Research Society, 55 (2004), 257-264.doi: 10.1057/palgrave.jors.2601689.
[3]	Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall and L. Stougie, Multiprocessor scheduling with rejection, SIAM Journal of Discrete Mathemtics, 13 (2000), 64-78.doi: 10.1137/S0895480196300522.
[4]	D. Biskup, Single-machine scheduling with learning considerations, European Journal of Operational Research, 115 (1999), 173-178.doi: 10.1016/S0377-2217(98)00246-X.
[5]	D. Biskup, A state-of-the-art review on scheduling with learning effects, European Journal of Operational Research, 188 (2008), 315-329.doi: 10.1016/j.ejor.2007.05.040.
[6]	Z. Cao and X. Yang, A PTAS for parallel batch scheduling with rejection and dynamic job arrivals, Theoretical Computer Science, 410 (2009), 2732-2745.doi: 10.1016/j.tcs.2009.04.006.
[7]	T. C. E. Cheng and G. Q. Wang, Single machine scheduling with learning effect considerations, Annals of Operations Research, 98 (2000), 273-290.doi: 10.1023/A:1019216726076.
[8]	Y. Cheng and S. Sun, Scheduling linear deteriorating jobs with rejection on a single machine, European Journal of Operational Research, 194 (2007), 18-27.doi: 10.1016/j.ejor.2007.11.047.
[9]	D. W. Engels, D. R. Karger, S. G. Kolliopoulos, S. Sengupta, R. N. Uma and J. Wein, Techniques for scheduling with rejection, Journal of Algorithms, 49 (2003), 175-191.doi: 10.1016/S0196-6774(03)00078-6.
[10]	E. Gerstl and G. Mosheiov, Scheduling on parallel identical machines with job-rejection and position-dependent processing times, Information Processing Letters, 112 (2012), 743-747.doi: 10.1016/j.ipl.2012.06.009.
[11]	V. S. Gordon and V. A. Strusevich, Single machine scheduling and due date assignment with positionally dependent processing times, European Journal of Operational Research, 198 (2009), 57-62.doi: 10.1016/j.ejor.2008.07.044.
[12]	C. J. Hsu, S. J. Yang and D. L. Yang, Two due date assignment problems with position-dependent processing time on a single machine, Computers and Industrial Engineering, 60 (2011), 796-800.doi: 10.1016/j.cie.2011.01.017.
[13]	A. Janiak and R. Rudek, Scheduling jobs under an aging effect, Journal of the Operational Research Society, 61 (2010), 1041-1048.doi: 10.1057/jors.2009.30.
[14]	H. W. Kuhn, The Hungarian method for the assignment problem, Naval Research Logistics Quarterly, 2 (1955), 83-97.doi: 10.1002/nav.3800020109.
[15]	W. H. Kuo and D. L. Yang, Minimizing the makespan in a single-machine scheduling problem with the cyclic process of an aging effect, Journal of the Operational Research Society, 59 (2008), 416-420.doi: 10.1057/palgrave.jors.2602363.
[16]	S. S Li and J. J. Yuan, Parallel-machine scheduling with deteriorating jobs and rejection, Theoretical Computer Science, 411 (2010), 3642-3650.doi: 10.1016/j.tcs.2010.06.008.
[17]	S. D. Liman, S. S. Panwalkar and S. Thongmee, Common due window size and location determination in a single machine scheduling problem, Journal of the Operational Research Society, 49 (1998), 1007-1010.
[18]	L. F. Lu, T. C. E. Cheng, J. J. Yuan and L. Q. Zhang, Bounded single-machine parallel-batch scheduling with release dates and rejection, Computers & Operations Research, 36 (2009), 2748-2751.doi: 10.1016/j.cor.2008.12.003.
[19]	L. F. Lu, L. Q. Zhang and J. J. Yuan, The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan, Theoretical Computer Science, 396 (2008), 283-289.doi: 10.1016/j.tcs.2008.02.015.
[20]	W. Luo and L. Chen, Approximation schemes for scheduling a maintenance and linear deteriorating jobs, Journal of Industrial and Management Optimization, 8 (2012), 271-283.doi: 10.3934/jimo.2012.8.271.
[21]	G. Mosheiov, Scheduling problems with a learning effect, European Journal of Operational Research, 132 (2001), 687-693.doi: 10.1016/S0377-2217(00)00175-2.
[22]	G. Mosheiov, Parallel machine scheduling with a learning effect, Journal of the Operational Research Society, 52 (2001), 1165-1169.doi: 10.1057/palgrave.jors.2601215.
[23]	G. Mosheiov, A note on scheduling deteriorating jobs, Mathematical and Computer Modelling, 41 (2005), 883-886.doi: 10.1016/j.mcm.2004.09.004.
[24]	G. Mosheiov and J. B. Sidney, Scheduling with general job-dependent learning curves, European Journal of Operational Research, 147 (2003), 665-670.doi: 10.1016/S0377-2217(02)00358-2.
[25]	S. S. Panwalkar, M. L. Smith and A. Seidmann, Common due date assignment to minimize total penalty for the one machine scheduling problem, Operations Research, 30 (1982), 391-399.doi: 10.1287/opre.30.2.391.
[26]	G. Qian, D. Han, L. Xu and H. Yang, Solving nonadditive traffic assignment problems: A self-adaptive projection-auxiliary problem method for variational inequalities, Journal of Industrial and Management Optimization, 9 (2013), 255-274.doi: 10.3934/jimo.2013.9.255.
[27]	A. Seidmann, S. S. Panwalkar and M. L. Smith, Optimal assignment of due dates for a single processor scheduling problem, International Journal of Production Research, 19 (1981), 393-399.doi: 10.1080/00207548108956667.
[28]	D. Shabtay and N. Gaspar, Two-machine flow-shop scheduling with rejection, Computers & Operations Research, 39 (2012), 1087-1096.doi: 10.1016/j.cor.2011.05.023.
[29]	D. Shabtay, N. Gaspar and L. Yedidsion, A bicriteria approach to scheduling a single machine with job rejection and positional penalties, Journal of Combinatorial Optimization, 23 (2012), 395-424.doi: 10.1007/s10878-010-9350-6.
[30]	C. C. Wu, P. H. Hsu, J. C. Chen and N. S. Wang, Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times, Computers & Operations Research, 38 (2011), 1025-1034.doi: 10.1016/j.cor.2010.11.001.
[31]	C. C. Wu, W. C. Lee and T. Chen, Heuristic algorithms for solving the maximum lateness scheduling problem with learning considerations, Computers and Industrial Engineering, 52 (2007), 124-132.doi: 10.1016/j.cie.2006.10.007.
[32]	Y. Xia, Convex hull of the orthogonal similarity set with applications in quadratic assignment problems, Journal of Industrial and Management Optimization, 9 (2013), 689-701.doi: 10.3934/jimo.2013.9.689.
[33]	Y. Yin, T. C. E. Cheng, J. Xu, S. R. Cheng and C. C. Wu, Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration, Journal of Industrial and Management Optimization, 9 (2013), 323-339.doi: 10.3934/jimo.2013.9.323.
[34]	L. Q. Zhang, L. F. Lu and J. J. Yuan, Single machine scheduling with release dates and rejection, European Journal of Operational Research, 198 (2009), 975-978.doi: 10.1016/j.ejor.2008.10.006.
[35]	C. L. Zhao and H. Y. Tang, Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan, Applied Mathematical Modelling, 34 (2010), 837-841.doi: 10.1016/j.apm.2009.07.002.