Premium
Two‐stage hybrid flow shop with recirculation
Author(s) -
Boudhar Mourad,
Meziani Nadjat
Publication year - 2010
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2009.00711.x
Subject(s) - heuristics , job shop scheduling , flow shop scheduling , mathematical optimization , computer science , stage (stratigraphy) , time complexity , scheduling (production processes) , flow (mathematics) , resolution (logic) , mathematics , algorithm , artificial intelligence , paleontology , schedule , geometry , biology , operating system
In this paper, we present two scheduling hybrid flow shop problems to minimize the makespan. In each problem, we have two stages. In the first problem, one machine at each stage is considered with recirculation of jobs in the second stage (machine). We prove that this first problem is polynomial and we present an algorithm for its resolution. The second problem consists of one machine in the first stage and two identical parallel machines in the second. Jobs can be recirculated a fixed number of times in the second stage. We show that the problem is NP‐hard and a polynomial subproblem is proposed. Linear program and heuristics are also presented with numerical experimentations.