• Previous Article
    Solutions for bargaining games with incomplete information: General type space and action space
  • JIMO Home
  • This Issue
  • Next Article
    On the convergence properties of a smoothing approach for mathematical programs with symmetric cone complementarity constraints
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  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 & 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 & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2018088

[2]

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

[3]

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

[4]

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

[5]

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

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

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-17. doi: 10.3934/jimo.2018058

[13]

Ta-Wei Hung, Ping-Ting Chen. On the optimal replenishment in a finite planning horizon with learning effect of setup costs. Journal of Industrial & Management Optimization, 2010, 6 (2) : 425-433. doi: 10.3934/jimo.2010.6.425

[14]

Cai-Tong Yue, Jing Liang, Bo-Fei Lang, Bo-Yang Qu. Two-hidden-layer extreme learning machine based wrist vein recognition system. Big Data & Information Analytics, 2017, 2 (1) : 59-68. doi: 10.3934/bdia.2017008

[15]

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

[16]

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

[17]

Anarina L. Murillo, Muntaser Safan, Carlos Castillo-Chavez, Elizabeth D. Capaldi Phillips, Devina Wadhera. Modeling eating behaviors: The role of environment and positive food association learning via a Ratatouille effect. Mathematical Biosciences & Engineering, 2016, 13 (4) : 841-855. doi: 10.3934/mbe.2016020

[18]

Xiaoming Yan, Minghui Zhang, Ke Liu, Yong Wang. Optimal ordering policies and sourcing strategies with supply disruption. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1147-1168. doi: 10.3934/jimo.2014.10.1147

[19]

Jerzy A. Filar, Prabhu Manyem, David M. Panton, Kevin White. A model for adaptive rescheduling of flights in emergencies (MARFE). Journal of Industrial & Management Optimization, 2007, 3 (2) : 335-356. doi: 10.3934/jimo.2007.3.335

[20]

Sanjoy Kumar Paul, Ruhul Sarker, Daryl Essam. Managing risk and disruption in production-inventory and supply chain systems: A review. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1009-1029. doi: 10.3934/jimo.2016.12.1009

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (42)
  • HTML views (394)
  • Cited by (0)

Other articles
by authors

[Back to Top]