• Previous Article
    On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints
  • JIMO Home
  • This Issue
  • Next Article
    Solutions for bargaining games with incomplete information: General type space and action space
July  2018, 14(3): 967-980. doi: 10.3934/jimo.2017085

Single-machine rescheduling problems with learning effect under disruptions

School of Management, Guangdong University of Technology, Gaungzhou, Guangdong 510520, China

* Corresponding author

Received  March 2016 Revised  August 2017 Published  July 2018 Early access  September 2017

Fund Project: The research is supported partially by the National Natural Science Foundation Committee of China grant 71571050,71502100,71401044.

Rescheduling in production planning means to schedule the sequenced jobs again together with a set of new arrived jobs so as to generate a new feasible schedule, which creates disruptions to any job between the original and adjusted position. In this paper, we study rescheduling problems with learning effect under disruption constraints to minimize several classical objectives, where learning effect means that the workers gain experience during the process of operation and make the actual processing time of jobs shorter than their normal processing time. The objectives are to find optimal sequences to minimize the makespan and the total completion time under a limit of the disruptions from the original schedule. For the considered objectives under a single disruption constraint or a disruption cost constraint, we propose polynomial-time algorithms and pseudo-polynomial time algorithms, respectively.

Citation: Mingbao Cheng, Shuxian Xiao, Guosheng Liu. Single-machine rescheduling problems with learning effect under disruptions. Journal of Industrial and Management Optimization, 2018, 14 (3) : 967-980. doi: 10.3934/jimo.2017085
References:
[1]

M. J. Anzanello and F. S. Fogliatto, Learning curve models and applications: Literature review and research directions, International Journal of Industrial Ergonomics, 41 (2011), 573-583.  doi: 10.1016/j.ergon.2011.05.001.

[2]

J. P. Arnaout, Rescheduling of parallel machines with stochastic processing and setup times, Journal of Manufacturing Systems, 33 (2014), 376-384.  doi: 10.1016/j.jmsy.2014.02.003.

[3]

M. Azizoglu and O. Alagoz, Parallel-machine rescheduling with machine disruptions, IIE Transactions, 37 (2007), 1113-1118.  doi: 10.1080/07408170500288133.

[4]

A. Bachman and A. Janiak, Scheduling job with position-dependent processing times, Journal of the Operational Research Society, 55 (2004), 257-264. 

[5]

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.

[6]

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.

[7]

M. B. Cheng and S. J. Sun, The single-machine scheduling problems with deteriorating jobs and learning effect, Zhejiang Univ. Science A, 7 (2006), 597-601. 

[8]

M. B. ChengP. R. TadikamallaJ. Shang and B. X. Zhang, Single machine scheduling problems with exponentially time-dependent learning effects, Journal of Manufacturing Systems, 34 (2015), 60-65.  doi: 10.1016/j.jmsy.2014.11.001.

[9]

Y. Chiu and C. J. Shih, Rescheduling strategies for integrating rush orders with preventive maintenance in a two-machine flow shop, International Journal of Production Research, 50 (2011), 5783-5794.  doi: 10.1080/00207543.2011.627887.

[10]

J. A. FilarP. ManyemD. M. Panton and K. White, A model for adaptive rescheduling of flights in emergencies, Journal of Industrial and Management Optimization, 3 (2007), 335-356.  doi: 10.3934/jimo.2007.3.335.

[11]

N. G. Hall and C. N. Potts, Rescheduling for new orders, Operations Research, 52 (2004), 440-453.  doi: 10.1287/opre.1030.0101.

[12]

N. G. Hall and C. N. Potts, Rescheduling for Job Unavailability, Operations Research, 58 (2010), 746-755.  doi: 10.1287/opre.1090.0751.

[13]

H. HoogeveenC. Lent and V. Tkindtal, Rescheduling for new orders on a single machine with setup times, European Journal of Operational Research, 223 (2012), 40-46.  doi: 10.1016/j.ejor.2012.05.046.

[14]

K. KatragjiniE. Vallada and R. Ruiz, Flow shop rescheduling under different types of disruption, International Journal of Production Research, 51 (2013), 780-797. 

[15]

L. Liu and H. Zhou, On the identical parallel-machine rescheduling with job rework disruption, Computers & Industrial Engineering, 66 (2013), 186-198.  doi: 10.1016/j.cie.2013.02.018.

[16]

Z. Liu and K. Ro Young, Rescheduling for machine disruption to minimize makespan and maximum lateness, Journal of Scheduling, 17 (2014), 339-352.  doi: 10.1007/s10951-014-0372-2.

[17]

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

[18]

M. Ozlen and M. Azizoglu, Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria, Journal of the Operational Research Society, 62 (2011), 152-164.  doi: 10.1057/jors.2009.157.

[19]

L. L. SunF. J. LuanY. Ying and K. Mao, Rescheduling optimization of steelmaking-continuous casting process based on the Lagrangian heuristic algorithm, Journal of Industrial and Management Optimization, 13 (2017), 1431-1448.  doi: 10.3934/jimo.2016081.

[20]

B. Vahedi-NouriP. FattahiM. Rohaninejad and R. Tavakkoli-Moghaddam, Minimizing the total completion time on a single machine with the learning effect and multiple availability constraints, Applied Mathematical Modelling, 37 (2013), 3126-3137.  doi: 10.1016/j.apm.2012.07.028.

[21]

J. B. WangM. Q. LiuN. Yin and P. Ji, Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects, Journal of Industrial and Management Optimization, 13 (2017), 1025-1039.  doi: 10.3934/jimo.2016060.

[22]

T. P. Wright, Factors Affecting the Cost of Airplanes, Journal of Aeronautical Sciences, 3 (1936), 122-128.  doi: 10.2514/8.155.

[23]

S. D. Wu, R. H. Storer and P. C. Chang, A rescheduling procedure for manufacturing systems under random disruptions, in: G. Fandel, T. Gulledge, A. Jone (Eds. ), New Directions for Operations Research in Manufacturing, Springer, Berlin, Germany, 1992, pp. 292-306. doi: 10.1007/978-3-642-77537-6_18.

[24]

B. B. Yang, Single machine rescheduling with new jobs arrivals and processing time compression, International Journal of Advanced Manufacture Technology, 34 (2007), 378-384.  doi: 10.1007/s00170-006-0590-7.

[25]

Y. Q. YinD. H. XuK. B. Sun and H. X. 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.

[26]

J. J. Yuan and Y. Mu, Rescheduling with release dates to minimize makespan under a limit on the maximum sequence disruption, European Journal of Operational Research, 182 (2007), 936-944. 

[27]

L. ZhangL. Gao and X. Li, A hybrid intelligent algorithm and rescheduling technique for job shop scheduling problems with disruptions, International Journal of Advanced Manufacturing Technology, 65 (2013), 1141-1156. 

[28]

C. Zhao and H. Tang, Rescheduling problems with deteriorating jobs under disruptions, Applied Mathematical Modelling, 34 (2010), 238-243.  doi: 10.1016/j.apm.2009.03.037.

show all references

References:
[1]

M. J. Anzanello and F. S. Fogliatto, Learning curve models and applications: Literature review and research directions, International Journal of Industrial Ergonomics, 41 (2011), 573-583.  doi: 10.1016/j.ergon.2011.05.001.

[2]

J. P. Arnaout, Rescheduling of parallel machines with stochastic processing and setup times, Journal of Manufacturing Systems, 33 (2014), 376-384.  doi: 10.1016/j.jmsy.2014.02.003.

[3]

M. Azizoglu and O. Alagoz, Parallel-machine rescheduling with machine disruptions, IIE Transactions, 37 (2007), 1113-1118.  doi: 10.1080/07408170500288133.

[4]

A. Bachman and A. Janiak, Scheduling job with position-dependent processing times, Journal of the Operational Research Society, 55 (2004), 257-264. 

[5]

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.

[6]

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.

[7]

M. B. Cheng and S. J. Sun, The single-machine scheduling problems with deteriorating jobs and learning effect, Zhejiang Univ. Science A, 7 (2006), 597-601. 

[8]

M. B. ChengP. R. TadikamallaJ. Shang and B. X. Zhang, Single machine scheduling problems with exponentially time-dependent learning effects, Journal of Manufacturing Systems, 34 (2015), 60-65.  doi: 10.1016/j.jmsy.2014.11.001.

[9]

Y. Chiu and C. J. Shih, Rescheduling strategies for integrating rush orders with preventive maintenance in a two-machine flow shop, International Journal of Production Research, 50 (2011), 5783-5794.  doi: 10.1080/00207543.2011.627887.

[10]

J. A. FilarP. ManyemD. M. Panton and K. White, A model for adaptive rescheduling of flights in emergencies, Journal of Industrial and Management Optimization, 3 (2007), 335-356.  doi: 10.3934/jimo.2007.3.335.

[11]

N. G. Hall and C. N. Potts, Rescheduling for new orders, Operations Research, 52 (2004), 440-453.  doi: 10.1287/opre.1030.0101.

[12]

N. G. Hall and C. N. Potts, Rescheduling for Job Unavailability, Operations Research, 58 (2010), 746-755.  doi: 10.1287/opre.1090.0751.

[13]

H. HoogeveenC. Lent and V. Tkindtal, Rescheduling for new orders on a single machine with setup times, European Journal of Operational Research, 223 (2012), 40-46.  doi: 10.1016/j.ejor.2012.05.046.

[14]

K. KatragjiniE. Vallada and R. Ruiz, Flow shop rescheduling under different types of disruption, International Journal of Production Research, 51 (2013), 780-797. 

[15]

L. Liu and H. Zhou, On the identical parallel-machine rescheduling with job rework disruption, Computers & Industrial Engineering, 66 (2013), 186-198.  doi: 10.1016/j.cie.2013.02.018.

[16]

Z. Liu and K. Ro Young, Rescheduling for machine disruption to minimize makespan and maximum lateness, Journal of Scheduling, 17 (2014), 339-352.  doi: 10.1007/s10951-014-0372-2.

[17]

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

[18]

M. Ozlen and M. Azizoglu, Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria, Journal of the Operational Research Society, 62 (2011), 152-164.  doi: 10.1057/jors.2009.157.

[19]

L. L. SunF. J. LuanY. Ying and K. Mao, Rescheduling optimization of steelmaking-continuous casting process based on the Lagrangian heuristic algorithm, Journal of Industrial and Management Optimization, 13 (2017), 1431-1448.  doi: 10.3934/jimo.2016081.

[20]

B. Vahedi-NouriP. FattahiM. Rohaninejad and R. Tavakkoli-Moghaddam, Minimizing the total completion time on a single machine with the learning effect and multiple availability constraints, Applied Mathematical Modelling, 37 (2013), 3126-3137.  doi: 10.1016/j.apm.2012.07.028.

[21]

J. B. WangM. Q. LiuN. Yin and P. Ji, Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects, Journal of Industrial and Management Optimization, 13 (2017), 1025-1039.  doi: 10.3934/jimo.2016060.

[22]

T. P. Wright, Factors Affecting the Cost of Airplanes, Journal of Aeronautical Sciences, 3 (1936), 122-128.  doi: 10.2514/8.155.

[23]

S. D. Wu, R. H. Storer and P. C. Chang, A rescheduling procedure for manufacturing systems under random disruptions, in: G. Fandel, T. Gulledge, A. Jone (Eds. ), New Directions for Operations Research in Manufacturing, Springer, Berlin, Germany, 1992, pp. 292-306. doi: 10.1007/978-3-642-77537-6_18.

[24]

B. B. Yang, Single machine rescheduling with new jobs arrivals and processing time compression, International Journal of Advanced Manufacture Technology, 34 (2007), 378-384.  doi: 10.1007/s00170-006-0590-7.

[25]

Y. Q. YinD. H. XuK. B. Sun and H. X. 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.

[26]

J. J. Yuan and Y. Mu, Rescheduling with release dates to minimize makespan under a limit on the maximum sequence disruption, European Journal of Operational Research, 182 (2007), 936-944. 

[27]

L. ZhangL. Gao and X. Li, A hybrid intelligent algorithm and rescheduling technique for job shop scheduling problems with disruptions, International Journal of Advanced Manufacturing Technology, 65 (2013), 1141-1156. 

[28]

C. Zhao and H. Tang, Rescheduling problems with deteriorating jobs under disruptions, Applied Mathematical Modelling, 34 (2010), 238-243.  doi: 10.1016/j.apm.2009.03.037.

[1]

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

[2]

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

[3]

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 and Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040

[4]

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

[5]

Hongwei Li, Yuvraj Gajpal, C. R. Bector. A survey of due-date related single-machine with two-agent scheduling problem. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1329-1347. doi: 10.3934/jimo.2019005

[6]

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

[7]

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

[8]

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 and Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071

[9]

Shuen Guo, Zhichao Geng, Jinjiang Yuan. Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021192

[10]

Ata Allah Taleizadeh, Biswajit Sarkar, Mohammad Hasani. Delayed payment policy in multi-product single-machine economic production quantity model with repair failure and partial backordering. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1273-1296. doi: 10.3934/jimo.2019002

[11]

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

[12]

Min Li, Jiahua Zhang, Yifan Xu, Wei Wang. Effect of disruption risk on a supply chain with price-dependent demand. Journal of Industrial and Management Optimization, 2020, 16 (6) : 3083-3103. doi: 10.3934/jimo.2019095

[13]

Émilie Chouzenoux, Henri Gérard, Jean-Christophe Pesquet. General risk measures for robust machine learning. Foundations of Data Science, 2019, 1 (3) : 249-269. doi: 10.3934/fods.2019011

[14]

Ana Rita Nogueira, João Gama, Carlos Abreu Ferreira. Causal discovery in machine learning: Theories and applications. Journal of Dynamics and Games, 2021, 8 (3) : 203-231. doi: 10.3934/jdg.2021008

[15]

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

[16]

Kebing Chen, Haijie Zhou, Dong Lei. Two-period pricing and ordering decisions of perishable products with a learning period for demand disruption. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3131-3163. doi: 10.3934/jimo.2020111

[17]

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

[18]

Chuanli Zhao. An fptas for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs. Journal of Industrial and Management Optimization, 2017, 13 (2) : 587-593. doi: 10.3934/jimo.2016033

[19]

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

[20]

Jiang Xie, Junfu Xu, Celine Nie, Qing Nie. Machine learning of swimming data via wisdom of crowd and regression analysis. Mathematical Biosciences & Engineering, 2017, 14 (2) : 511-527. doi: 10.3934/mbe.2017031

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (341)
  • HTML views (1107)
  • Cited by (1)

Other articles
by authors

[Back to Top]