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.

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

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

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

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

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

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

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

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

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

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

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

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

[14]

H. W. Kuhn, The Hungarian method for the assignment problem,, Naval Research Logistics Quarterly, 2 (1955), 83. 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. 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. 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.

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

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

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

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

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

[23]

G. Mosheiov, A note on scheduling deteriorating jobs,, Mathematical and Computer Modelling, 41 (2005), 883. 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. 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. 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. 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. doi: 10.1080/00207548108956667.

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

[14]

H. W. Kuhn, The Hungarian method for the assignment problem,, Naval Research Logistics Quarterly, 2 (1955), 83. 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. 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. 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.

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

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

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

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

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

[23]

G. Mosheiov, A note on scheduling deteriorating jobs,, Mathematical and Computer Modelling, 41 (2005), 883. 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. 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. 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. 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. doi: 10.1080/00207548108956667.

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

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

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

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

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

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

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

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

[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]

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

[19]

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

[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

2017 Impact Factor: 0.994

Metrics

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

[Back to Top]