• Previous Article
    Multiple common due-dates assignment and optimal maintenance activity scheduling with linear deteriorating jobs
  • JIMO Home
  • This Issue
  • Next Article
    Algorithms for single-machine scheduling problem with deterioration depending on a novel model
April  2017, 13(2): 697-711. doi: 10.3934/jimo.2016041

Parallel-machine scheduling with potential disruption and positional-dependent processing times

1. 

Faculty of Science, Kunming University of Science and Technology, Kunming 650500, China

2. 

Business School, Hunan University, Changsha, Hunan 410082, China

3. 

Department of Business Administration, Fu Jen Catholic University, New Taipei City, Taiwan

* Corresponding author: Mengqi Liu

Received  October 2015 Revised  January 2016 Published  May 2016

Fund Project: This paper was supported in part by the National Natural Science Foundation of China (71301022,71471057); and in part by the Personnel Training Fund of Kunming University of Science and Technology (KKSY201407098).

In this paper, we address the scheduling problem with positional-dependent processing times in a disruptive environment, in which there is a possibility that some of the machines become unavailable for a certain period of time with a certain probability due to a disruption at a particular time. By positional-dependent processing times, we mean that the actual processing time of a job depends on its processing position on a machine. Since some machines may be unavailable for a certain period of time, both non-resumable and resumable cases are considered. The objective is to minimize the expected total completion time. For various cases, we provide the complexity results and present efficient pseudo-polynomial time algorithms for the corresponding problems.

Citation: 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 and Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041
References:
[1]

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.

[2]

G. H. Hardy, J. E. Littlewood and G. Polya, Inequalities, Cambridge: Cambridge University Press, 1934.

[3]

R. L. GrahamE. L. LawlerJ. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic machine scheduling: A survey, Annals of Discrete Mathematics, 5 (1979), 287-326.  doi: 10.1016/S0167-5060(08)70356-X.

[4]

J.-Y Kung and M.-H. Shu, Some cheduling problems on a single machine with general job effects of position-dependent learning and start-time-dependent deterioration, Asia-Pacific Journal of Operational Research, 32 (2015), 1550002 (21pages).  doi: 10.1142/S0217595915500025.

[5]

C.-Y. Lee, Machine scheduling with an availability constraint. Special Issue on "Optimization on Scheduling Application", Journal of global optimination, 9 (1996), 395-416.  doi: 10.1007/BF00121681.

[6]

C.-Y. LeeL. Lei and M. Pinedo, Current trends in deterministic scheduling, Annals of Operations Research, 70 (1997), 1-41.  doi: 10.1023/A:1018909801944.

[7]

C.-Y. Lee and S. D. Liman, Single machine flow-time scheduling with scheduled maintenance, Acta Informatica, 29 (1992), 375-382.  doi: 10.1007/BF01178778.

[8]

C.-Y. Lee and G. Yu, Single machine scheduling under potential disruption, Operations Research Letters, 35 (2007), 541-548.  doi: 10.1016/j.orl.2006.08.005.

[9]

C.-Y. Lee and G. Yu, Parallel-machine scheduling under potential disruption, Optimization Letters, 2 (2008), 27-37.  doi: 10.1007/s11590-006-0041-2.

[10]

A. LevinG. Mosheiov and A. Sarig, Scheduling a maintenance activity on parallel identical machines, Naval Research Logistics, 56 (2009), 33-41.  doi: 10.1002/nav.20324.

[11]

Y. MaC. Chu and C. Zuo, A survey of scheduling with deterministic machine availability constraints, Computers & Industrial Engineering, 58 (2010), 199-211.  doi: 10.1016/j.cie.2009.04.014.

[12]

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

[13]

J.-B. Wang, Single-machine scheduling problems with the effects of learning and deterioration, Omega, 35 (2007), 397-402.  doi: 10.1016/j.omega.2005.07.008.

[14]

J.-B. Wang and Z.-Q. Xia, Flow-shop scheduling with a learning effec}t, Journal of the Operational Research Society, 56 (2005), 1325-1330.  doi: 10.1057/palgrave.jors.2601856.

[15]

X.-Y. Wang and J.-J. Wang, Scheduling deteriorating jobs with a learning effect on unrelated parallel machines, Applied Mathematical Modelling, 38 (2014), 5231-5238.  doi: 10.1016/j.apm.2014.04.002.

[16]

E. Sanlaville and G. Schmidt, Machine scheduling with availability constraints, Acta Informatica, 35 (1998), 795-811.  doi: 10.1007/s002360050143.

[17]

G. Schmidt, Scheduling with limited machine availability, European Journal of Operational Research, 121 (2000), 1-15.  doi: 10.1016/S0377-2217(98)00367-1.

[18]

D.-L. Yang and W.-H. Kuo, A single-machine scheduling problem with learning effects in intermittent batch production, Computers & Industrial Engineering, 57 (2009), 762-765.  doi: 10.1016/j.cie.2009.02.003.

[19]

Y. YinM. LiuJ. Hao and M. Zhou, Single machine scheduling with job position-dependent learning and time-dependent deterioration, IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 42 (2012), 192-200.  doi: 10.1109/TSMCA.2011.2147305.

[20]

Y. YinW. WuT. C. E. Cheng and C.-C. Wu, Single-machine scheduling with time-dependent and position-dependent deteriorating jobs, International Journal of Computer Integrated Manufacturing, 28 (2015), 781-790.  doi: 10.1080/0951192X.2014.900872.

[21]

Y. YinW. WuT. C. E. Cheng and C.-C. Wu, Due date assignment and single-machine scheduling with generalized positional deteriorating jobs and deteriorating multi-maintenance activities, International Journal of Production Research, 52 (2014), 2311-2326. 

[22]

Y. YinD. Xu and X. Huang, Notes on "some single-machine scheduling problems with general position-dependent and time-dependent learning effects", Information Sciences, 181 (2011), 2209-2217.  doi: 10.1016/j.ins.2011.01.018.

[23]

Y. YinD. XuK. Sun and H. Li, Some scheduling problems with general position-dependent and time-dependent learning effects, Information Sciences, 179 (2009), 2416-2425.  doi: 10.1016/j.ins.2009.02.015.

[24]

C. ZhaoY. YinT. 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, 10 (2014), 691-700.  doi: 10.3934/jimo.2014.10.691.

show all references

References:
[1]

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.

[2]

G. H. Hardy, J. E. Littlewood and G. Polya, Inequalities, Cambridge: Cambridge University Press, 1934.

[3]

R. L. GrahamE. L. LawlerJ. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic machine scheduling: A survey, Annals of Discrete Mathematics, 5 (1979), 287-326.  doi: 10.1016/S0167-5060(08)70356-X.

[4]

J.-Y Kung and M.-H. Shu, Some cheduling problems on a single machine with general job effects of position-dependent learning and start-time-dependent deterioration, Asia-Pacific Journal of Operational Research, 32 (2015), 1550002 (21pages).  doi: 10.1142/S0217595915500025.

[5]

C.-Y. Lee, Machine scheduling with an availability constraint. Special Issue on "Optimization on Scheduling Application", Journal of global optimination, 9 (1996), 395-416.  doi: 10.1007/BF00121681.

[6]

C.-Y. LeeL. Lei and M. Pinedo, Current trends in deterministic scheduling, Annals of Operations Research, 70 (1997), 1-41.  doi: 10.1023/A:1018909801944.

[7]

C.-Y. Lee and S. D. Liman, Single machine flow-time scheduling with scheduled maintenance, Acta Informatica, 29 (1992), 375-382.  doi: 10.1007/BF01178778.

[8]

C.-Y. Lee and G. Yu, Single machine scheduling under potential disruption, Operations Research Letters, 35 (2007), 541-548.  doi: 10.1016/j.orl.2006.08.005.

[9]

C.-Y. Lee and G. Yu, Parallel-machine scheduling under potential disruption, Optimization Letters, 2 (2008), 27-37.  doi: 10.1007/s11590-006-0041-2.

[10]

A. LevinG. Mosheiov and A. Sarig, Scheduling a maintenance activity on parallel identical machines, Naval Research Logistics, 56 (2009), 33-41.  doi: 10.1002/nav.20324.

[11]

Y. MaC. Chu and C. Zuo, A survey of scheduling with deterministic machine availability constraints, Computers & Industrial Engineering, 58 (2010), 199-211.  doi: 10.1016/j.cie.2009.04.014.

[12]

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

[13]

J.-B. Wang, Single-machine scheduling problems with the effects of learning and deterioration, Omega, 35 (2007), 397-402.  doi: 10.1016/j.omega.2005.07.008.

[14]

J.-B. Wang and Z.-Q. Xia, Flow-shop scheduling with a learning effec}t, Journal of the Operational Research Society, 56 (2005), 1325-1330.  doi: 10.1057/palgrave.jors.2601856.

[15]

X.-Y. Wang and J.-J. Wang, Scheduling deteriorating jobs with a learning effect on unrelated parallel machines, Applied Mathematical Modelling, 38 (2014), 5231-5238.  doi: 10.1016/j.apm.2014.04.002.

[16]

E. Sanlaville and G. Schmidt, Machine scheduling with availability constraints, Acta Informatica, 35 (1998), 795-811.  doi: 10.1007/s002360050143.

[17]

G. Schmidt, Scheduling with limited machine availability, European Journal of Operational Research, 121 (2000), 1-15.  doi: 10.1016/S0377-2217(98)00367-1.

[18]

D.-L. Yang and W.-H. Kuo, A single-machine scheduling problem with learning effects in intermittent batch production, Computers & Industrial Engineering, 57 (2009), 762-765.  doi: 10.1016/j.cie.2009.02.003.

[19]

Y. YinM. LiuJ. Hao and M. Zhou, Single machine scheduling with job position-dependent learning and time-dependent deterioration, IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 42 (2012), 192-200.  doi: 10.1109/TSMCA.2011.2147305.

[20]

Y. YinW. WuT. C. E. Cheng and C.-C. Wu, Single-machine scheduling with time-dependent and position-dependent deteriorating jobs, International Journal of Computer Integrated Manufacturing, 28 (2015), 781-790.  doi: 10.1080/0951192X.2014.900872.

[21]

Y. YinW. WuT. C. E. Cheng and C.-C. Wu, Due date assignment and single-machine scheduling with generalized positional deteriorating jobs and deteriorating multi-maintenance activities, International Journal of Production Research, 52 (2014), 2311-2326. 

[22]

Y. YinD. Xu and X. Huang, Notes on "some single-machine scheduling problems with general position-dependent and time-dependent learning effects", Information Sciences, 181 (2011), 2209-2217.  doi: 10.1016/j.ins.2011.01.018.

[23]

Y. YinD. XuK. Sun and H. Li, Some scheduling problems with general position-dependent and time-dependent learning effects, Information Sciences, 179 (2009), 2416-2425.  doi: 10.1016/j.ins.2009.02.015.

[24]

C. ZhaoY. YinT. 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, 10 (2014), 691-700.  doi: 10.3934/jimo.2014.10.691.

[1]

Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1795-1807. doi: 10.3934/jimo.2021044

[2]

Si-Han Wang, Dan-Yang Lv, Ji-Bo Wang. Research on position-dependent weights scheduling with delivery times and truncated sum-of-processing-times-based learning effect. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022066

[3]

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 and Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691

[4]

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

[5]

Ji-Bo Wang, Bo Zhang, Hongyu He. A unified analysis for scheduling problems with variable processing times. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1063-1077. doi: 10.3934/jimo.2021008

[6]

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 and Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

[7]

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

[8]

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 and Management Optimization, 2017, 13 (2) : 1025-1039. doi: 10.3934/jimo.2016060

[9]

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 and Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088

[10]

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 and Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323

[11]

Reza Alizadeh Foroutan, Javad Rezaeian, Milad Shafipour. Bi-objective unrelated parallel machines scheduling problem with worker allocation and sequence dependent setup times considering machine eligibility and precedence constraints. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021190

[12]

Tsuguhito Hirai, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance optimization of parallel-distributed processing with checkpointing for cloud environment. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1423-1442. doi: 10.3934/jimo.2018014

[13]

Min-Fan He, Li-Ning Xing, Wen Li, Shang Xiang, Xu Tan. Double layer programming model to the scheduling of remote sensing data processing tasks. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1515-1526. doi: 10.3934/dcdss.2019104

[14]

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

[15]

P. Liu, Xiwen Lu. Online scheduling of two uniform machines to minimize total completion times. Journal of Industrial and Management Optimization, 2009, 5 (1) : 95-102. doi: 10.3934/jimo.2009.5.95

[16]

Xuewen Huang, Xiaotong Zhang, Sardar M. N. Islam, Carlos A. Vega-Mejía. An enhanced Genetic Algorithm with an innovative encoding strategy for flexible job-shop scheduling with operation and processing flexibility. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2943-2969. doi: 10.3934/jimo.2019088

[17]

Xingong Zhang. Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon. Journal of Industrial and Management Optimization, 2020, 16 (1) : 231-244. doi: 10.3934/jimo.2018148

[18]

Alireza Goli, Taha Keshavarz. Just-in-time scheduling in identical parallel machine sequence-dependent group scheduling problem. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021124

[19]

Ji-Bo Wang, Dan-Yang Lv, Shi-Yun Wang, Chong Jiang. Resource allocation scheduling with deteriorating jobs and position-dependent workloads. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022011

[20]

Yunqing Zou, Zhengkui Lin, Dongya Han, T. C. Edwin Cheng, Chin-Chia Wu. Two-agent integrated scheduling of production and distribution operations with fixed departure times. Journal of Industrial and Management Optimization, 2022, 18 (2) : 985-1007. doi: 10.3934/jimo.2021005

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (180)
  • HTML views (414)
  • Cited by (3)

[Back to Top]