Predictive-reactive Strategy for Flowshop Rescheduling Problem: Minimizing the Total Weighted Waiting Times and Instability

Abstract

Due to the fourth revolution experiencing, referred to as Industry 4.0, many production firms are devoted to integrating new technological tools to their manufacturing process. One of them, is rescheduling the tasks on the machines responding to disruptions. While, for static scheduling, the efficiency criteria measure the performance of scheduling systems, in dynamic environments, the stability criteria are also used to assess the impact of jobs deviation. In this paper, a new performance measure is investigated for a flowshop rescheduling problem. This one considers simultaneously the total weighted waiting time as the efficiency criterion, and the total weighted completion time deviation as the stability criterion. This fusion could be a very helpful and significant measure for real life industrial systems. Two disruption types are considered: jobs arrival and jobs cancellation. Thus, a Mixed Integer Linear Programming (MILP) model is developed, as well as an iterative predictive-reactive strategy for dealing with the online part. At last, two heuristic methods are proposed and discussed, in terms of solution quality and computing time.

Keywords

Rescheduling / flowshop / predictive-reactive strategy / weighted waiting time / stability / weighted completion time deviation

References

[1] Anand R, Aggarwal D, Kumar V. A comparative analysis of optimization solvers. Journal of Statistics and Management Systems, 2017, 20(4): 623-635.

[2] Bakker M, Tsui K L. Dynamic resource allocation for efficient patient scheduling: A data-driven approach. Journal of Systems Science and Systems Engineering, 2017, 26(4): 448-462.

[3] Bierwirth C, Mattfeld D C. Production scheduling and rescheduling with genetic algorithms. Evolutionary Computation, 1999, 7(1): 1-17.

[4] Chaari T, Chaabane S, Loukil T, Trentesaux D. A genetic algorithm for robust hybrid flow shop scheduling. International Journal of Computer Integrated Manufacturing, 2011, 24(9): 821-833.

[5] Chiu Y, Shih C J. Rescheduling strategies for integrating rush orders with preventive maintenance in a two-machine flow shop. International Journal of Production Research, 2012, 50(20): 5783-5794.

[6] Curry J, Peters B. Rescheduling parallel machines with stepwise increasing tardiness and machine assignment stability objectives. International Journal of Production Research, 2005, 43(15): 3231-3246.

[7] Duenas A, Petrovic D. An approach to predictive-reactive scheduling of parallel machines subject to disruptions. Annals of Operations Research, 2008, 159(1): 65-82.

[8] El-Bouri A. A cooperative dispatching approach for minimizing mean tardiness in a dynamic flowshop. Computers & Operations Research, 2012, 39(7): 1305-1314.

[9] Foumani M, Jenab K. Analysis of flexible robotic cells with improved pure cycle. International Journal of Computer Integrated Manufacturing, 2013, 26(3): 201-215.

[10] Foumani M, Razeghi A, Smith-Miles K. Stochastic optimization of two-machine flow shop robotic cells with controllable inspection times: From theory toward practice. Robotics and Computer-Integrated Manufacturing, 2020, 61: 101822.

[11] Guo Y, Huang M, Wang Q, Leon V J. Single-machine rework rescheduling to minimize maximum waiting-times with fixed sequence of jobs and ready times. Computers & Industrial Engineering, 2016, 91: 262-273.

[12] Guo Y, Wang Q, Huang M. Rescheduling with release time to minimize sum of waiting time considering waiting constraint of original loads. Acta Automatica Sinica, 2013, 39(12): 2100-2110.

[13] Guo Y, Xie X (2017). Two mixed integer programming formulations on single machine to reschedule repaired jobs for minimizing the total waiting-time. In 2017 Chinese Automation Congress (CAC):2129–2133. IEEE, 2017.

[14] Gürel S, Körpeoğlu E, Aktürk M S. An anticipative scheduling approach with controllable processing times. Computers & Operations Research, 2010, 37(6): 1002-1013.

[15] Hall N G, Liu Z, Potts C N. Rescheduling for multiple new orders. INFORMS Journal on Computing, 2017, 19(4): 633-645.

[16] Hall N G, Potts C N. Rescheduling for new orders. Operations Research, 2004, 52(3): 440-453.

[17] Han Y, Gong D, Jin Y, Pan Q. Evolutionary multi-objective blocking lot-streaming flow shop scheduling with machine breakdowns. IEEE Transactions on Cybernetics, 2019, 49(1): 184-197.

[18] Han Y, Gong D, Jin Y, Pan Q. Evolutionary multi-objective blocking lot-streaming flow shop scheduling with machine breakdowns. IEEE Transactions on Cybernetics, 2017, 49(1): 184-197.

[19] He X, Dong S, Zhao N. Research on rush order insertion rescheduling problem under hybrid flow shop based on nsga-iii. International Journal of Production Research, 2020, 58(4): 1161-1177.

[20] Herrmann J W (2006). Handbook of Production Scheduling Volume 89. Springer Science & Business Media, 2006.

[21] Hoogeveen H, Lenté C, T’kindt V. Rescheduling for new orders on a single machine with setup times. European Journal of Operational Research, 2012, 223(1): 40-46.

[22] Ivanov D, Dolgui A, Sokolov B, Werner F, Ivanova M. A dynamic model and an algorithm for short-term supply chain scheduling in the smart factory industry 4.0. International Journal of Production Research, 2016, 54(2): 386-402.

[23] Jun S, Lee S, Chun H. Learning dispatching rules using random forest in flexible job shop scheduling problems. International Journal of Production Research, 2019, 57(10): 3290-3310.

[24] Jurcisin R, Sebo J. Basic production scheduling concept software application in a deterministic mechanical production environment. Acta Simulatio, 2015, 1(4): 1-4.

[25] Kan A R (2012). Machine Scheduling Problems: Classification, Complexity and Computations. Springer Science & Business Media, 2012.

[26] Katragjini K, Vallada E, Ruiz R. Flow shop rescheduling under different types of disruption. International Journal of Production Research, 2013, 51(3): 780-797.

[27] Katragjini K, Vallada E, Ruiz R (2015). Rescheduling flow-shops under simultaneous disruptions. In 2015 International Conference on Industrial Engineering and Systems Management (IESM): 84–91. IEEE, 2015.

[28] Khorsi M, Chaharsooghi S K, Ali B A, Ali H K. A multi-objective multi-period model for humanitarian relief logistics with split delivery and multiple uses of vehicles. Journal of Systems Science and Systems Engineering, 2020, 29: 360-378.

[29] Kianfar K, Ghomi S F, Jadid A O. Study of stochastic sequence-dependent flexible flow shop via developing a dispatching rule and a hybrid ga. Engineering Applications of Artificial Intelligence, 2012, 25(3): 494-506.

[30] Kovalyov M Y, Kress D, Meiswinkel S, Pesch E (2016). A parallel machine schedule updating game with compensations and zero risk. Technical report, working paper, National Academy of Sciences of Belarus and University of Siegen, 2016.

[31] Li J Q, Pan Q K, Mao K. A discrete teaching-learning-based optimisation algorithm for realistic flowshop rescheduling problems. Engineering Applications of Artificial Intelligence, 2015, 37: 279-292.

[32] Li J Q, Pan Q K, Mao K. A hybrid fruit fly optimization algorithm for the realistic hybrid flowshop rescheduling problem in steelmaking systems. IEEE Transactions on Automation Science and Engineering, 2015, 13(2): 932-949.

[33] Li R K, Shyu Y T, Adiga S. A heuristic rescheduling algorithm for computer-based production scheduling systems. The International Journal of Production Research, 1993, 31(8): 1815-1826.

[34] Li Z, Ierapetritou M. Process scheduling under uncertainty: Review and challenges. Computers & Chemical Engineering, 2008, 32(4–5): 715-727.

[35] Liu F, Wang S, Hong Y, Yue X. On the robust and stable flowshop scheduling under stochastic and dynamic disruptions. IEEE Transactions on Engineering Management, 2017, 64(4): 539-553.

[36] Liu L. Outsourcing and rescheduling for a two-machine flow shop with the disruption of new arriving jobs: A hybrid variable neighborhood search algorithm. Computers & Industrial Engineering, 2019, 130: 198-221.

[37] Liu L, Zhou H. Open shop rescheduling under singular machine disruption. Computer Integrated Manufacturing Systems, 2013, 10(10): 2467-2480.

[38] Liu W, Jin Y, Price M. New scheduling algorithms and digital tool for dynamic permutation flowshop with newly arrived order. International Journal of Production Research, 2017, 55(11): 3234-3248.

[39] Liu Z, Ro Y K. Rescheduling for machine disruption to minimize makespan and maximum lateness. Journal of Scheduling, 2014, 17(4): 339-352.

[40] Lodree E J, Jang W, Klein C M. A new rule for minimizing the number of tardy jobs in dynamic flow shops. European Journal of Operational Research, 2004, 159(1): 258-263.

[41] Mason S J, Jin S, Wessels C M. Rescheduling strategies for minimizing total weighted tardiness in complex job shops. International Journal of Production Research, 2004, 42(3): 613-628.

[42] Moeuf A, Pellerin R, Lamouri S, Tamayo G S, Barbaray R. The industrial management of smes in the era of industry 4.0. International Journal of Production Research, 2018, 56(3): 1118-1136.

[43] Muluk A, Akpolat H, Xu J. Scheduling problems — An overview. Journal of Systems Science and Systems Engineering, 2003, 12(4): 481-492.

[44] Nagasawa K, Ikeda Y, Irohara T. Robust flow shop scheduling with random processing times for reduction of peak power consumption. Simulation Modelling Practice and Theory, 2015, 59: 102-113.

[45] Nouiri M, Bekrar A, Trentesaux D. An energy-efficient scheduling and rescheduling method for production and logistics systems. International Journal of Production Research, 2020, 58(11): 3263-3283.

[46] Nurre S G, Sharkey T C. Online scheduling problems with flexible release dates: Applications to infrastructure restoration. Computers & Operations Research, 2018, 92: 1-16.

[47] Ouelhadj D, Petrovic S. A survey of dynamic scheduling in manufacturing systems. Journal of Scheduling, 2009, 12(4): 417-431.

[48] Peng K, Pan Q K, Gao L, Li X, Das S, Zhang B. A multi-start variable neighbourhood descent algorithm for hybrid flowshop rescheduling. Swarm and Evolutionary Computation, 2019, 45: 92-112.

[49] Peng K, Pan Q K, Gao L, Zhang B, Pang X. An improved artificial bee colony algorithm for real-world hybrid flowshop rescheduling in steelmaking-refining-continuous casting process. Computers & Industrial Engineering, 2018, 122: 235-250.

[50] Pfeiffer A, Kádár B, Monostori L. Stability-oriented evaluation of rescheduling strategies, by using simulation. Computers in Industry, 2007, 58(7): 630-643.

[51] Pinedo M, Zacharias C, Zhu N. Scheduling in the service industries: An overview. Journal of Systems Science and Systems Engineering, 2015, 24(1): 1-48.

[52] Qin W, Zhang J, Song D. An improved ant colony algorithm for dynamic hybrid flow shop scheduling with uncertain processing time. Journal of Intelligent Manufacturing, 2018, 29(4): 891-904.

[53] Rahmani D, Heydari M. Robust and stable flow shop scheduling with unexpected arrivals of new jobs and uncertain processing times. Journal of Manufacturing Systems, 2014, 33(1): 84-92.

[54] Rahmani D, Heydari M, Makui A, Zandieh M. A new approach to reducing the effects of stochastic disruptions in flexible flow shop problems with stability and nervousness. International Journal of Management Science and Engineering Management, 2013, 8(3): 173-178.

[55] Rahmani D, Ramezanian R. A stable reactive approach in dynamic flexible flow shop scheduling with unexpected disruptions: A case study. Computers & Industrial Engineering, 2016, 98: 360-372.

[56] Rangsaritratsamee R, Ferrell W G, Kurz M B. Dynamic rescheduling that simultaneously considers efficiency and stability. Computers & Industrial Engineering, 2004, 46(1): 1-15.

[57] Sabuncuoglu I, Karabuk S. Rescheduling frequency in an fms with uncertain processing times and unreliable machines. Journal of Manufacturing Systems, 1999, 18(4): 268-283.

[58] Salido M A, Escamilla J, Barber F, Giret A. Rescheduling in job-shop problems for sustainable manufacturing systems. Journal of Cleaner Production, 2017, 162: S121-S132.

[59] Tang D, Dai M, Salido M A, Giret A. Energy-efficient dynamic scheduling for a flexible flow shop using an improved particle swarm optimization. Computers in Industry, 2016, 81: 82-95.

[60] Tighazoui A, Sauvey C, Sauer N (2020). New efficiency-stability criterion in a rescheduling problem with dynamic jobs weights.In 2020 7th International Conference on Control, Decision and Information Technologies (CoDIT), volume 1: 475–480. IEEE, 2020.

[61] Tokola H, Ahlroth L, Niemi E. A comparison of rescheduling policies for online flow shops to minimize tardiness. Engineering Optimization, 2014, 46(2): 165-180.

[62] Trabelsi W, Sauvey C, Sauer N. Heuristics and metaheuristics for mixed blocking constraints flowshop scheduling problems. Computers & Operations Research, 2012, 39(11): 2520-2527.

[63] Uhlmann I R, Frazzon E M. Production rescheduling review: Opportunities for industrial integration and practical applications. Journal of Manufacturing Systems, 2018, 49: 186-193.

[64] Unal A T, Uzsoy R, Kiran A S. Rescheduling on a single machine with part-type dependent setup times and deadlines. Annals of Operations Research, 1997, 70: 93-113.

[65] Valledor P, Gomez A, Priore P, Puente J. Solving multi-objective rescheduling problems in dynamic permutation flow shop environments with disruptions. International Journal of Production Research, 2018, 56(19): 6363-6377.

[66] Vieira G E, Herrmann J W, Lin E. Rescheduling manufacturing systems: A framework of strategies, policies, and methods. Journal of Scheduling, 2003, 6(1): 39-62.

[67] Wang D, Yin Y, Cheng TCE. Parallel-machine rescheduling with job unavailability and rejection. Omega, 2018, 81: 246-260.

[68] Weng W, Wei X, Fujimura S. Dynamic routing strategies for JIT production in hybrid flow shops. Computers & Operations Research, 2012, 39(12): 3316-33242.

[69] Wu S D, Storer R H, Chang P C. One-machine rescheduling heuristics with efficiency and stability as criteria. Computers & Operations Research, 1993, 20(1): 1-14.

[70] Hu Y H, Yan J Q, Ye F F, Yu J H. Flow shop rescheduling problem under rush orders. Journal of Zhejiang University-SCIENCE A, 2005, 6(10): 1040-1046.

[71] Yang B, Geunes J. Predictive-reactive scheduling on a single resource with uncertain future jobs. European Journal of Operational Research, 2008, 189(3): 1267-1283.

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

[73] Zhang G, Cai X, Wong C K. Scheduling two groups of jobs with incomplete information. Journal of Systems Science and Systems Engineering, 2003, 12(1): 73-81.

[74] Zhang L, Gao L, Li X. A hybrid genetic algorithm and tabu search for a multi-objective dynamic job shop scheduling problem. International Journal of Production Research, 2013, 51(12): 3516-3531.

[75] Zhao X, Liu N, Zhao S, Wu J, Zhang K, Zhang R. Research on the work-rest scheduling in the manual order picking systems to consider human factors. Journal of Systems Science and Systems Engineering, 2019, 28(3): 344-355.