Abstract
This paper studies a flow shop scheduling problem with three stages. At the first stage, different parts of a job are independently manufactured on m unrelated parallel machines. At the second stage, the manufactured parts are collected and transferred to the assembly stage where the parts are assembled into a final product. In this problem we considered sequence dependent setup times at each stage, and the objective to be minimize is the total tardiness. Motivated by the computational complexity and the practical relevance of the problem, we propose a heuristic based on General Variable Neighborhood Search with random VND (RVND) local search procedure to obtain near-optimal solutions. In the proposed RVND, a neighborhood is selected according to a selection probability that is self-updated with the number of improvements obtained by the neighborhood. As shaking procedure, we use a destruction-construction strategy that is used in the Iterated Greedy meta-heuristic. The effectiveness of the presented heuristic is evaluated by comparing its results to a basic GVNS, a Simulated Annealing proposed in the literature, and the CPLEX solver used to solve the mixed integer programming model of the problem. The obtained results have been statistically analysed.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ruiz, R., Stützle, T.: An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives. Eur. J. Oper. Res. 187(3), 1143–1159 (2008)
Du, J., Leung, J.Y.T.: Minimizing total tardiness on one machine is NP-hard. Math. Oper. Res. 15(3), 483–495 (1990)
Hatami, S., Ebrahimnejad, S., Tavakkoli-Moghaddam, R., Maboudian, Y.: Two meta-heuristics for three-stage assembly flowshop scheduling with sequence-dependent setup times. Int. J. Adv. Manuf. Technol. 50(9–12), 1153–1164 (2010)
Andrés, C., Hatami, S.: The three stage assembly permutation flow shop scheduling problem. In: V International Conference on Industrial Engineering and Industrial Management, pp. 867–875 (2011)
Maleki-Darounkolaei, A., Modiri, M., Tavakkoli-Moghaddam, R., Seyyedi, I.: A three-stage assembly flow shop scheduling problem with blocking and sequence-dependent set up times. J. Indust. Eng. Int. 8(1), 1–7 (2012)
Allahverdi, A., Aydilek, H.: The two stage assembly flow shop scheduling problem to minimize total tardiness. J. Intell. Manuf. 26, 1–13 (2013)
Hansen, P., Mladenović, N., Pérez, J.A.M.: Variable neighbourhood search: methods and applications. 4OR 6(4), 319–360 (2008)
Ruiz, R., Stützle, T.: A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur. J. Oper. Res. 177(3), 2033–2049 (2007)
Subramanian, A., Drummond, L.M.D.A., Bentes, C., Ochi, L.S., Farias, R.: A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Comput. Oper. Res. 37(11), 1899–1911 (2010)
Acknowledgments
The authors thanks the financial support of CNPq, CAPES and FAPEMIG, Brazilian research agencies.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Campos, S.C., Arroyo, J.E.C., Tavares, R.G. (2017). A General VNS Heuristic for a Three-Stage Assembly Flow Shop Scheduling Problem. In: Madureira, A., Abraham, A., Gamboa, D., Novais, P. (eds) Intelligent Systems Design and Applications. ISDA 2016. Advances in Intelligent Systems and Computing, vol 557. Springer, Cham. https://doi.org/10.1007/978-3-319-53480-0_94
Download citation
DOI: https://doi.org/10.1007/978-3-319-53480-0_94
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-53479-4
Online ISBN: 978-3-319-53480-0
eBook Packages: EngineeringEngineering (R0)