Reentrant open shop scheduling problem with time lags and no-wait constraints

In this work, we consider the two-machine reentrant open shop scheduling problem with no-wait and exact time lags constraints. The objective is to minimize the makespan. We first prove that this problem is NP-hard in the strong sense, then we provide some polynomial sub-problems. To solve the genera...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2024-06, Vol.166, p.106595, Article 106595
Main Authors: Alioui, Kenza, Amrouche, Karim, Boudhar, Mourad
Format: Article
Language:English
Subjects:
Metaheuristic
No-wait
Open shop
Reentrance
Time lags
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this work, we consider the two-machine reentrant open shop scheduling problem with no-wait and exact time lags constraints. The objective is to minimize the makespan. We first prove that this problem is NP-hard in the strong sense, then we provide some polynomial sub-problems. To solve the general problem, a heuristic and metaheuristics with hybridizations are proposed with numerical experiments. •A new scheduling problem on a two-machine Reentrant Open Shop with Time Lags and No-Wait constraints is considered.•A new NP-hard problem and four polynomial sub-problems are presented.•Lower Bounds are proposed.•A heuristic H1, a Genetic Algorithm GA, and two hybridization algorithms (H1GA and GAH1) are developed.•Computational experiments are carried out which show the effectiveness of the proposed algorithms.
ISSN:0305-0548
1873-765X
DOI:10.1016/j.cor.2024.106595