• 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 & 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.  Google Scholar

[2]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[16]

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

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

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

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

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

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

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

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

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

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

[2]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[16]

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

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

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

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

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

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

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

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

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

[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 & Management Optimization, 2021  doi: 10.3934/jimo.2021044

[2]

Karl-Peter Hadeler, Frithjof Lutscher. Quiescent phases with distributed exit times. Discrete & Continuous Dynamical Systems - B, 2012, 17 (3) : 849-869. doi: 10.3934/dcdsb.2012.17.849

[3]

Lekbir Afraites, Abdelghafour Atlas, Fahd Karami, Driss Meskine. Some class of parabolic systems applied to image processing. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1671-1687. doi: 10.3934/dcdsb.2016017

[4]

Shan-Shan Lin. Due-window assignment scheduling with learning and deterioration effects. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021081

[5]

Omer Gursoy, Kamal Adli Mehr, Nail Akar. Steady-state and first passage time distributions for waiting times in the $ MAP/M/s+G $ queueing model with generally distributed patience times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021078

[6]

Cécile Carrère, Grégoire Nadin. Influence of mutations in phenotypically-structured populations in time periodic environment. Discrete & Continuous Dynamical Systems - B, 2020, 25 (9) : 3609-3630. doi: 10.3934/dcdsb.2020075

[7]

Yuyue Zhang, Jicai Huang, Qihua Huang. The impact of toxins on competition dynamics of three species in a polluted aquatic environment. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3043-3068. doi: 10.3934/dcdsb.2020219

[8]

Haripriya Barman, Magfura Pervin, Sankar Kumar Roy, Gerhard-Wilhelm Weber. Back-ordered inventory model with inflation in a cloudy-fuzzy environment. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1913-1941. doi: 10.3934/jimo.2020052

[9]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3141-3161. doi: 10.3934/dcds.2020401

[10]

Weiyi Zhang, Zuhan Liu, Ling Zhou. Dynamics of a nonlocal diffusive logistic model with free boundaries in time periodic environment. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3767-3784. doi: 10.3934/dcdsb.2020256

[11]

Bo Duan, Zhengce Zhang. A reaction-diffusion-advection two-species competition system with a free boundary in heterogeneous environment. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021067

[12]

Jing Feng, Bin-Guo Wang. An almost periodic Dengue transmission model with age structure and time-delayed input of vector in a patchy environment. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3069-3096. doi: 10.3934/dcdsb.2020220

[13]

Yunfei Lv, Rong Yuan, Yuan He. Wavefronts of a stage structured model with state--dependent delay. Discrete & Continuous Dynamical Systems, 2015, 35 (10) : 4931-4954. doi: 10.3934/dcds.2015.35.4931

[14]

Jiaquan Liu, Xiangqing Liu, Zhi-Qiang Wang. Sign-changing solutions for a parameter-dependent quasilinear equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1779-1799. doi: 10.3934/dcdss.2020454

[15]

Hai-Yang Jin, Zhi-An Wang. The Keller-Segel system with logistic growth and signal-dependent motility. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3023-3041. doi: 10.3934/dcdsb.2020218

[16]

Paul Deuring. Spatial asymptotics of mild solutions to the time-dependent Oseen system. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021044

[17]

Ying Sui, Huimin Yu. Singularity formation for compressible Euler equations with time-dependent damping. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021062

[18]

Yuta Tanoue. Improved Hoeffding inequality for dependent bounded or sub-Gaussian random variables. Probability, Uncertainty and Quantitative Risk, 2021, 6 (1) : 53-60. doi: 10.3934/puqr.2021003

[19]

Wen-Bin Yang, Yan-Ling Li, Jianhua Wu, Hai-Xia Li. Dynamics of a food chain model with ratio-dependent and modified Leslie-Gower functional responses. Discrete & Continuous Dynamical Systems - B, 2015, 20 (7) : 2269-2290. doi: 10.3934/dcdsb.2015.20.2269

[20]

Irena PawŃow, Wojciech M. Zajączkowski. Global regular solutions to three-dimensional thermo-visco-elasticity with nonlinear temperature-dependent specific heat. Communications on Pure & Applied Analysis, 2017, 16 (4) : 1331-1372. doi: 10.3934/cpaa.2017065

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (72)
  • HTML views (412)
  • Cited by (3)

[Back to Top]