July  2014, 10(3): 691-700. doi: 10.3934/jimo.2014.10.691

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, China

2. 

State Key Laboratory Breeding Base of Nuclear Resources and Environment, East China Institute of Technology, Nanchang, Jiangxi 330013, China

3. 

Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, China

4. 

Department of Statistics, Feng Chia University, Taichung

Received  April 2013 Revised  June 2013 Published  November 2013

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.
Citation: Chuanli Zhao, Yunqiang Yin, T. C. E. Cheng, Chin-Chia Wu. Single-machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial & Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691
References:
[1]

G. I. Adamopoulos and C. P. Pappis, Single machine scheduling with flow allowances,, Journal of the Operational Research Society, 47 (1996), 1280. Google Scholar

[2]

A. Bachman and A. Janiak, Scheduling jobs with position-dependent processing times,, Journal of the Operational Research Society, 55 (2004), 257. doi: 10.1057/palgrave.jors.2601689. Google Scholar

[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. doi: 10.1137/S0895480196300522. Google Scholar

[4]

D. Biskup, Single-machine scheduling with learning considerations,, European Journal of Operational Research, 115 (1999), 173. doi: 10.1016/S0377-2217(98)00246-X. Google Scholar

[5]

D. Biskup, A state-of-the-art review on scheduling with learning effects,, European Journal of Operational Research, 188 (2008), 315. doi: 10.1016/j.ejor.2007.05.040. Google Scholar

[6]

Z. Cao and X. Yang, A PTAS for parallel batch scheduling with rejection and dynamic job arrivals,, Theoretical Computer Science, 410 (2009), 2732. doi: 10.1016/j.tcs.2009.04.006. Google Scholar

[7]

T. C. E. Cheng and G. Q. Wang, Single machine scheduling with learning effect considerations,, Annals of Operations Research, 98 (2000), 273. doi: 10.1023/A:1019216726076. Google Scholar

[8]

Y. Cheng and S. Sun, Scheduling linear deteriorating jobs with rejection on a single machine,, European Journal of Operational Research, 194 (2007), 18. doi: 10.1016/j.ejor.2007.11.047. Google Scholar

[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. doi: 10.1016/S0196-6774(03)00078-6. Google Scholar

[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. doi: 10.1016/j.ipl.2012.06.009. Google Scholar

[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. doi: 10.1016/j.ejor.2008.07.044. Google Scholar

[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. doi: 10.1016/j.cie.2011.01.017. Google Scholar

[13]

A. Janiak and R. Rudek, Scheduling jobs under an aging effect,, Journal of the Operational Research Society, 61 (2010), 1041. doi: 10.1057/jors.2009.30. Google Scholar

[14]

H. W. Kuhn, The Hungarian method for the assignment problem,, Naval Research Logistics Quarterly, 2 (1955), 83. doi: 10.1002/nav.3800020109. Google Scholar

[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. doi: 10.1057/palgrave.jors.2602363. Google Scholar

[16]

S. S Li and J. J. Yuan, Parallel-machine scheduling with deteriorating jobs and rejection,, Theoretical Computer Science, 411 (2010), 3642. doi: 10.1016/j.tcs.2010.06.008. Google Scholar

[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. Google Scholar

[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. doi: 10.1016/j.cor.2008.12.003. Google Scholar

[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. doi: 10.1016/j.tcs.2008.02.015. Google Scholar

[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. doi: 10.3934/jimo.2012.8.271. Google Scholar

[21]

G. Mosheiov, Scheduling problems with a learning effect,, European Journal of Operational Research, 132 (2001), 687. doi: 10.1016/S0377-2217(00)00175-2. Google Scholar

[22]

G. Mosheiov, Parallel machine scheduling with a learning effect,, Journal of the Operational Research Society, 52 (2001), 1165. doi: 10.1057/palgrave.jors.2601215. Google Scholar

[23]

G. Mosheiov, A note on scheduling deteriorating jobs,, Mathematical and Computer Modelling, 41 (2005), 883. doi: 10.1016/j.mcm.2004.09.004. Google Scholar

[24]

G. Mosheiov and J. B. Sidney, Scheduling with general job-dependent learning curves,, European Journal of Operational Research, 147 (2003), 665. doi: 10.1016/S0377-2217(02)00358-2. Google Scholar

[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. doi: 10.1287/opre.30.2.391. Google Scholar

[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. doi: 10.3934/jimo.2013.9.255. Google Scholar

[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. doi: 10.1080/00207548108956667. Google Scholar

[28]

D. Shabtay and N. Gaspar, Two-machine flow-shop scheduling with rejection,, Computers & Operations Research, 39 (2012), 1087. doi: 10.1016/j.cor.2011.05.023. Google Scholar

[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. doi: 10.1007/s10878-010-9350-6. Google Scholar

[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. doi: 10.1016/j.cor.2010.11.001. Google Scholar

[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. doi: 10.1016/j.cie.2006.10.007. Google Scholar

[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. doi: 10.3934/jimo.2013.9.689. Google Scholar

[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. doi: 10.3934/jimo.2013.9.323. Google Scholar

[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. doi: 10.1016/j.ejor.2008.10.006. Google Scholar

[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. doi: 10.1016/j.apm.2009.07.002. Google Scholar

show all references

References:
[1]

G. I. Adamopoulos and C. P. Pappis, Single machine scheduling with flow allowances,, Journal of the Operational Research Society, 47 (1996), 1280. Google Scholar

[2]

A. Bachman and A. Janiak, Scheduling jobs with position-dependent processing times,, Journal of the Operational Research Society, 55 (2004), 257. doi: 10.1057/palgrave.jors.2601689. Google Scholar

[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. doi: 10.1137/S0895480196300522. Google Scholar

[4]

D. Biskup, Single-machine scheduling with learning considerations,, European Journal of Operational Research, 115 (1999), 173. doi: 10.1016/S0377-2217(98)00246-X. Google Scholar

[5]

D. Biskup, A state-of-the-art review on scheduling with learning effects,, European Journal of Operational Research, 188 (2008), 315. doi: 10.1016/j.ejor.2007.05.040. Google Scholar

[6]

Z. Cao and X. Yang, A PTAS for parallel batch scheduling with rejection and dynamic job arrivals,, Theoretical Computer Science, 410 (2009), 2732. doi: 10.1016/j.tcs.2009.04.006. Google Scholar

[7]

T. C. E. Cheng and G. Q. Wang, Single machine scheduling with learning effect considerations,, Annals of Operations Research, 98 (2000), 273. doi: 10.1023/A:1019216726076. Google Scholar

[8]

Y. Cheng and S. Sun, Scheduling linear deteriorating jobs with rejection on a single machine,, European Journal of Operational Research, 194 (2007), 18. doi: 10.1016/j.ejor.2007.11.047. Google Scholar

[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. doi: 10.1016/S0196-6774(03)00078-6. Google Scholar

[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. doi: 10.1016/j.ipl.2012.06.009. Google Scholar

[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. doi: 10.1016/j.ejor.2008.07.044. Google Scholar

[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. doi: 10.1016/j.cie.2011.01.017. Google Scholar

[13]

A. Janiak and R. Rudek, Scheduling jobs under an aging effect,, Journal of the Operational Research Society, 61 (2010), 1041. doi: 10.1057/jors.2009.30. Google Scholar

[14]

H. W. Kuhn, The Hungarian method for the assignment problem,, Naval Research Logistics Quarterly, 2 (1955), 83. doi: 10.1002/nav.3800020109. Google Scholar

[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. doi: 10.1057/palgrave.jors.2602363. Google Scholar

[16]

S. S Li and J. J. Yuan, Parallel-machine scheduling with deteriorating jobs and rejection,, Theoretical Computer Science, 411 (2010), 3642. doi: 10.1016/j.tcs.2010.06.008. Google Scholar

[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. Google Scholar

[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. doi: 10.1016/j.cor.2008.12.003. Google Scholar

[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. doi: 10.1016/j.tcs.2008.02.015. Google Scholar

[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. doi: 10.3934/jimo.2012.8.271. Google Scholar

[21]

G. Mosheiov, Scheduling problems with a learning effect,, European Journal of Operational Research, 132 (2001), 687. doi: 10.1016/S0377-2217(00)00175-2. Google Scholar

[22]

G. Mosheiov, Parallel machine scheduling with a learning effect,, Journal of the Operational Research Society, 52 (2001), 1165. doi: 10.1057/palgrave.jors.2601215. Google Scholar

[23]

G. Mosheiov, A note on scheduling deteriorating jobs,, Mathematical and Computer Modelling, 41 (2005), 883. doi: 10.1016/j.mcm.2004.09.004. Google Scholar

[24]

G. Mosheiov and J. B. Sidney, Scheduling with general job-dependent learning curves,, European Journal of Operational Research, 147 (2003), 665. doi: 10.1016/S0377-2217(02)00358-2. Google Scholar

[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. doi: 10.1287/opre.30.2.391. Google Scholar

[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. doi: 10.3934/jimo.2013.9.255. Google Scholar

[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. doi: 10.1080/00207548108956667. Google Scholar

[28]

D. Shabtay and N. Gaspar, Two-machine flow-shop scheduling with rejection,, Computers & Operations Research, 39 (2012), 1087. doi: 10.1016/j.cor.2011.05.023. Google Scholar

[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. doi: 10.1007/s10878-010-9350-6. Google Scholar

[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. doi: 10.1016/j.cor.2010.11.001. Google Scholar

[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. doi: 10.1016/j.cie.2006.10.007. Google Scholar

[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. doi: 10.3934/jimo.2013.9.689. Google Scholar

[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. doi: 10.3934/jimo.2013.9.323. Google Scholar

[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. doi: 10.1016/j.ejor.2008.10.006. Google Scholar

[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. doi: 10.1016/j.apm.2009.07.002. Google Scholar

[1]

Xianyu Yu, Dar-Li Yang, Dequn Zhou, Peng Zhou. Multi-machine scheduling with interval constrained position-dependent processing times. Journal of Industrial & Management Optimization, 2018, 14 (2) : 803-815. doi: 10.3934/jimo.2017076

[2]

Hongwei Li, Yuvraj Gajpal, C. R. Bector. A survey of due-date related single-machine with two-agent scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-19. doi: 10.3934/jimo.2019005

[3]

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

[4]

Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71

[5]

Bin Zheng, Min Fan, Mengqi Liu, Shang-Chia Liu, Yunqiang Yin. Parallel-machine scheduling with potential disruption and positional-dependent processing times. Journal of Industrial & Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041

[6]

Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial & Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323

[7]

Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088

[8]

Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial & Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825

[9]

Xingong Zhang. Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2018148

[10]

Sachiko Ishida. Global existence and boundedness for chemotaxis-Navier-Stokes systems with position-dependent sensitivity in 2D bounded domains. Discrete & Continuous Dynamical Systems - A, 2015, 35 (8) : 3463-3482. doi: 10.3934/dcds.2015.35.3463

[11]

Chunlai Liu, Yanpeng Fan, Chuanli Zhao, Jianjun Wang. Multiple common due-dates assignment and optimal maintenance activity scheduling with linear deteriorating jobs. Journal of Industrial & Management Optimization, 2017, 13 (2) : 713-720. doi: 10.3934/jimo.2016042

[12]

Hua-Ping Wu, Min Huang, W. H. Ip, Qun-Lin Fan. Algorithms for single-machine scheduling problem with deterioration depending on a novel model. Journal of Industrial & Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040

[13]

Ganggang Li, Xiwen Lu, Peihai Liu. The coordination of single-machine scheduling with availability constraints and delivery. Journal of Industrial & Management Optimization, 2016, 12 (2) : 757-770. doi: 10.3934/jimo.2016.12.757

[14]

Muminu O. Adamu, Aderemi O. Adewumi. A survey of single machine scheduling to minimize weighted number of tardy jobs. Journal of Industrial & Management Optimization, 2014, 10 (1) : 219-241. doi: 10.3934/jimo.2014.10.219

[15]

Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058

[16]

Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071

[17]

Ji-Bo Wang, Mengqi Liu, Na Yin, Ping Ji. Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1025-1039. doi: 10.3934/jimo.2016060

[18]

Lalida Deeratanasrikul, Shinji Mizuno. Multiple-stage multiple-machine capacitated lot-sizing and scheduling with sequence-dependent setup: A case study in the wheel industry. Journal of Industrial & Management Optimization, 2017, 13 (1) : 413-428. doi: 10.3934/jimo.2016024

[19]

Wael Bahsoun, Christopher Bose, Anthony Quas. Deterministic representation for position dependent random maps. Discrete & Continuous Dynamical Systems - A, 2008, 22 (3) : 529-540. doi: 10.3934/dcds.2008.22.529

[20]

Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial & Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (9)
  • HTML views (0)
  • Cited by (13)

[Back to Top]