Chain-reentrant shop with an exact time lag: new results

Karim Amrouche (1, 2) , Mourad Boudhar (2) , Mohamed Bendraouche (2) , Farouk Yalaoui (3)

1 Faculty of Economics and Management sciences, University of Algiers 3
2 Laboratoire RECITS, Faculté de Mathématiques,USTHB, BP 32, Bab-Ezzouar, El-Alia 16111, Alger, Algérie
3 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

The two-machine chain-reentrant shop scheduling with the objective of minimizing the makespan, assumes that the tasks pass from the first machine to the second and return back to the first machine. In this paper, we consider the same problem in which an exact time lag between the two operations on the first machine is imposed. In Amrouche and Boudhar (2016) the authors proved that this problem is NP-hard in the strong sense in the case of identical time lags l j = L. We propose heuristic algorithms with empirical results for the latter. In addition, we establish a new NP-hardness result and some polynomial cases.

Keywords: flowshop; chain-reentrant; time lag; complexity; heuristics

Domains: Operations Research [cs.RO]

Karim Amrouche, Mourad Boudhar, Mohamed Bendraouche, Farouk Yalaoui. Chain-reentrant shop with an exact time lag: new results. International Journal of Production Research, 2016, 55 (1), pp.285-295. ⟨10.1080/00207543.2016.1205235⟩. ⟨hal-02491672⟩