Mixed integer linear programming models for flow shop scheduling with a demand plan of job types.

*(English)*Zbl 07176676Summary: This paper presents two mixed integer linear programming (MILP) models that extend two basic Flow Shop Scheduling problems: \(\text{Fm}/\text{prmu}/\text{C}_{ \max}\) and \(\text{Fm}/\text{block}/\text{C}_{ \max}\). This extension incorporates the concept of an overall demand plan for types of jobs or products. After using an example to illustrate the new problems under study, we evaluated the new models and analyzed their behaviors when applied to instances found in the literature and industrial instances of a case study from Nissan’s plant in Barcelona. CPLEX solver was used as a solution tool and obtained acceptable results, allowing us to conclude that MILP can be used as a method for solving Flow Shop Scheduling problems with an overall demand plan.

##### MSC:

90B | Operations research and management science |

##### Keywords:

flow shop scheduling problem; mixed model sequencing problem; mixed model assembly lines; overall demand plan; mixed integer linear programming##### Software:

CPLEX
PDF
BibTeX
XML
Cite

\textit{J. Bautista-Valhondo} and \textit{R. Alfaro-Pozo}, CEJOR, Cent. Eur. J. Oper. Res. 28, No. 1, 5--23 (2020; Zbl 07176676)

Full Text:
DOI

##### References:

[1] | Aggoune, R., Minimizing the makespan for the flow shop scheduling problem with availability constraints, Eur J Oper Res, 153, 3, 534-543 (2004) · Zbl 1099.90536 |

[2] | Bautista, J.; Cano, A., Solving mixed model sequencing problem in assembly lines with serial workstations with work overload minimisation and interruption rules, Eur J Oper Res, 210, 3, 495-513 (2011) · Zbl 1213.90109 |

[3] | Bautista-Valhondo, J.; Alfaro-Pozo, R., An expert system to minimize operational costs in mixed-model sequencing problems with activity factor, Expert Syst Appl, 104, 185-201 (2018) |

[4] | Bautista, J.; Cano, A.; Companys, R.; Ribas, I., Solving the Fm|block|Cmax problem using Bounded Dynamic Programming, Eng Appl Artif Intell, 25, 6, 1235-1245 (2012) |

[5] | Bautista, J.; Alfaro-Pozo, R.; Batalla-García, C.; Viles, E.; Ormazábal, M.; Lleó, A., Minimizing lost-work costs in a mixed-model assembly line, Closing the gap between practice and research in industrial engineering. Lecture notes in management and industrial engineering (2018), Cham: Springer, Cham |

[6] | Caraffa, V.; Ianes, S.; Bagchi, Tp; Sriskandarajah, C., Minimizing makespan in a blocking flowshop using genetic algorithms, Int J Prod Econ, 70, 2, 101-115 (2001) |

[7] | Fernandez-Viagas, V.; Ruiz, R.; Framinan, Jm, A new vision of approximate methods for the permutation flowshop to minimise makespan: state-of-the-art and computational evaluation, Eur J Oper Res, 257, 3, 707-721 (2017) · Zbl 1394.90271 |

[8] | Grabowski, J.; Pempera, J., The permutation flow shop problem with blocking. A tabu search approach, Omega, 35, 3, 302-311 (2007) |

[9] | Graham, Rl; Lawler, El; Lenstra, Jk; Rinnooy Kan, Ahg, Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann Discret Math, 5, 287-326 (1979) · Zbl 0411.90044 |

[10] | Hall, Ng; Sriskandarajah, C., Survey of machine scheduling problems with blocking and no-wait in process, Oper Res, 44, 3, 510-525 (1996) · Zbl 0864.90060 |

[11] | Han, Yy; Pan, Qk; Li, Jq, An improved artificial bee colony algorithm for the blocking flowshop scheduling problema, Int J Adv Manuf Technol, 60, 1149-1159 (2012) |

[12] | Hoogeveen, Ja; Lenstra, Jk; Veltman, B., Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard, Eur J Oper Res, 89, 1, 172-175 (1996) · Zbl 0908.90164 |

[13] | Lin, Sw; Ying, Kc, Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm, Omega, 41, 2, 383-389 (2013) |

[14] | Logendran, R.; Sriskandarajah, C., Two-machine group scheduling problem with blocking and anticipatory setups, Eur J Oper Res, 69, 3, 467-481 (1993) · Zbl 0784.90039 |

[15] | Nawaz, M.; Enscore, Ee; Ham, I., A heuristic algorithm for the m-machine, n-job flow-shop sequencing problema, Omega, 11, 1, 91-95 (1983) |

[16] | Nouri, N.; Ladhari, T., Evolutionary multiobjective optimization for the multi-machine flow shop scheduling problem under blocking, Ann Oper Res (2017) · Zbl 1398.90159 |

[17] | Osman, Ih; Potts, Cn, Simulated annealing for permutation flow-shop scheduling, Omega, 17, 6, 551-557 (1989) |

[18] | Ozolins, A., Improved bounded dynamic programming algorithm for solving the blocking flow shop problem, Cent Eur J Oper Res (2017) · Zbl 07024038 |

[19] | Pan, Qk; Wang, L., Effective heuristics for the blocking flowshop scheduling problem with makespan minimization, Omega, 40, 2, 218-229 (2012) |

[20] | Pinedo, Ml, Scheduling (theory, algorithms, and systems) (2016), Berlin: Springer International Publishing, Berlin |

[21] | Reeves, Cr, A genetic algorithm for flowshop sequencing, Comput Oper Res, 22, 1, 5-13 (1995) · Zbl 0815.90097 |

[22] | Ribas, I.; Companys, R.; Tort-Martorell, X., An iterated greedy algorithm for the flowshop scheduling problem with blocking, Omega, 39, 3, 293-301 (2011) |

[23] | Ronconi, Dp, A note on constructive heuristics for the flowshop problem with blocking, Int J Prod Econ, 87, 1, 39-48 (2004) |

[24] | Ronconi, Dp, A branch-and-bound algorithm to minimize the makespan in a flowshop with blocking, Ann Oper Res, 138, 1, 53-65 (2005) · Zbl 1091.90075 |

[25] | Taillard, E., Some efficient heuristic methods for the flow shop sequencing problema, Eur J Oper Res, 47, 1, 65-74 (1990) · Zbl 0702.90043 |

[26] | Taillard, E., Benchmarks for basic scheduling problems, Eur J Oper Res, 64, 2, 278-285 (1993) · Zbl 0769.90052 |

[27] | Tasgetiren, Mf; Kizilay, D.; Pan, Qk; Suganthanc, Pn, Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion, Comput Oper Res, 77, 111-126 (2017) · Zbl 1391.90323 |

[28] | Ying, Kc; Liao, Cj, An ant colony system for permutation flow-shop sequencing, Comput Oper Res, 31, 5, 791-801 (2004) · Zbl 1048.90113 |

[29] | Yu, W.; Hoogeveen, H.; Lenstra, Jk, Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard, J Sched, 7, 5, 333-348 (2004) · Zbl 1154.90506 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.