Flowshop scheduling with machine deterioration based on job sequences
Article Sidebar
Main Article Content
This paper addresses the two-machine permutation flowshop problem with deterioration. The objectives are minimizing the makespan and the average tardiness. Jobs have a baseline process time in each machine and have a due date. The actual time to process a job depends on the machine performance level at the start of each job, which is a function of the previously processed jobs and their wear/deterioration effect on the machine. The article proposes multiple heuristics and a comprehensive set of experiments. The results indicate that as a group, the heuristics generate solutions that are very close to the optimal for both criteria. Furthermore, no heuristic approach is dominant for all experimental conditions, thus heuristic selection to solve practical problems should be based on the specific problem characteristics.
(1) Fei H, Li Q, Sun D. A survey of recent research on optimization models and algorithms for operations management from the process view. Scientific Programming. 2017. https://doi.org/10.1155/2017/7219656.
(2) Long J, Zheng Z, Gao X, Pardalos PM. Scheduling a realistic hybrid flow shop with stage skipping and adjustable processing time in steel plants. Applied Soft Computing. 2018;64:536-549. https://doi.org/10.1016/j.asoc.2017.12.044
(3) Khare A, Agrawal S. Scheduling hybrid flowshop with sequence-dependent setup times and due windows to minimize total weighted earliness and tardiness. Computers & Industrial Engineering. 2019;135:780-792. https://doi.org/10.1016/j.cie.2019.06.057
(4) Pan QK, Ruiz R, Alfaro-Fernández P. Iterated search methods for earliness and tardiness minimization in hybrid flowshops with due windows. Computers & Operations Research. 2017;80:50-60. https://doi.org/10.1016/j.cor.2016.11.022
(5) Reisman A, Kumar A, Motwani J. Flowshop scheduling/sequencing research: A statistical review of the literature, 1952-1994. IEEE transactions on Engineering Management. 1994;44(3):316-329. https://doi.org/10.1109/17.618173.
(6) Tohmé F, Frutos M. The non-permutation flow-shop scheduling problem: a literature review. Omega. 2018;77:143-153. https://doi.org/10.1016/j.omega.2017.05.010.
(7) Neufeld JS, Gupta JN, Buscher U. A comprehensive review of flowshop group scheduling literature. Computers & Operations Research. 2016;70:56-74. https://doi.org/10.1016/j.cor.2015.12.006.
(8) Kononov A, Gawiejnowicz S. NP-hard cases in scheduling deteriorating jobs on dedicated machines. Journal of the Operational Research Society. 2001;52(6): 708–717. https://doi.org/10.1057/palgrave.jors.2601117.
(9) Wang, JB, Xia ZQ. Flow shop scheduling problems with deteriorating jobs under dominating machines. Journal of the Operational Research Society. 2006;57(2): 220–226. https://doi.org/10.1057/palgrave.jors.2601959.
(10) Wang JB, Ng CTD, Cheng TCE, Liu LL. Minimizing total completion time in a two-machine flow shop with deteriorating jobs. Applied Mathematics and Computation. 2006;180(1):185–193. https://doi.org/10.1016/j.amc.2005.11.162
(11) Lee WC, Wu CC, Wen CC, Chung YH. A two-machine flowshop makespan scheduling problem with deteriorating jobs. Computers & Industrial Engineering. 2008;54(4):737-749. https://doi.org/10.1016/j.cie.2007.10.010.
(12) Lee WC, Shiau YR, Chen SK, Wu CC. A two-machine flowshop scheduling problem with deteriorating jobs and blocking. International Journal of Production Economics. 2010;124(1), 188-197. https://doi.org/10.1016/j.ijpe.2009.11.001
(13) Wang JB, Ji P, Cheng TCE, Wang D. Minimizing makespan in a two-machine flow shop with effects of deterioration and learning. Optimization letters. 2012;6(7): 1393-1409. https://doi.org/10.1007/s11590-011-0334-y.
(14) Wang JB, Wang MZ. Minimizing makespan in three-machine flow shops with deteriorating jobs. Computers & Operations Research. 2013;40(2):547-557. https://doi.org/10.1016/j.cor.2012.08.006
(15) Sun LH, Ge CC, Zhang W, Wang JB, Lu YY. Permutation flowshop scheduling with simple linear deterioration. Engineering Optimization. 2018;51(8):1281-1300. https://doi.org/10.1080/0305215X.2018.1519558.
(16) Bank M, Ghomi SF, Jolai F, Behnamian J. Two-machine flow shop total tardiness scheduling problem with deteriorating jobs. Applied Mathematical Modelling. 2013;36(11):5418-26. https://doi.org/10.1016/j.apm.2011.12.010
(17) Lee WC, Yeh WC, Chung YH. Total tardiness minimization in permutation flowshop with deterioration consideration. Applied Mathematical Modelling. 2014;38(13):3081-3092. https://doi.org/10.1016/j.apm.2013.11.031
(18) Sánchez-Herrera S, Montoya-Torres JR, Solano-Charris EL. Flow shop scheduling problem with position-dependent processing times. Computers & Operations Research. 2019;111:325-345. https://doi.org/10.1016/j.cor.2019.06.015
(19) Ruiz-Torres AJ, Paletta G, Pérez E. Parallel machine scheduling to minimize the makespan with sequence dependent deteriorating effects. Computers & Operations Research. 2013;40(8):2051-61. https://doi.org/10.1016/j.cor.2013.02.018
(20) Santos VLA, Arroyo JEC. Iterated greedy with random variable neighborhood descent for scheduling jobs on parallel machines with deterioration effect. Electronic Notes in Discrete Mathematics. 2017;58:55-62. https://doi.org/10.1016/j.endm.2017.03.008
(21) De Araújo O, Dhein G, Fampa M. Minimizing the makespan on parallel machines with sequence dependent deteriorating effects. In: XLIX Simpósio Brasileiro de Pesquisa Operacional. Blumenau-SC: SOBRAPO – Sociedade Brasileira Pesquisa Operacional; 2017. p. 3556–67.
(22) Pérez E, Ambati RR, Ruiz-Torres AJ. Maximising the number of on-time jobs on parallel servers with sequence dependent deteriorating processing times and periodic maintenance. International Journal of Operational Research. 2018;32(3):267-289.
(23) Ding J, Shen L, Lü Z, Peng B. Parallel machine scheduling with completion-time-based criteria and sequence-dependent deterioration. Computers & Operations Research. 2019;103:35-45. https://doi.org/10.1016/j.cor.2018.10.016
(24) Khamadaliyev DM, Ulyanov VN. Ulyanov DO, Taylakov KS, Serdyuk RZ. et al. A Software Solution for Automatic Optimization of Logistics During Well Drilling and Flowback Operations. Russian Oil and Gas Technologies Magazine. 55:104-111. https://rogtecmagazine.com/rogtec-issue-55/.
(25) Johnson SM. Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly. 1954;1(1):61-68.https://doi.org/10.1002/nav.3800010110
Accepted 2021-03-01
Published 2021-05-18
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Authors grant the journal and Universidad del Valle the economic rights over accepted manuscripts, but may make any reuse they deem appropriate for professional, educational, academic or scientific reasons, in accordance with the terms of the license granted by the journal to all its articles.
Articles will be published under the Creative Commons 4.0 BY-NC-SA licence (Attribution-NonCommercial-ShareAlike).