Open AccessA Computational Study of the Two-Machine No-Wait Flow Shop Scheduling Problem Subject to Unequal Release Dates and Non-Availability Constraints
Author(s) -
Mohamed Labidi,
Anis Kooli,
Talel Ladhari,
Anis Gharbi,
Umar S. Suryahatmaja
Publication year - 2018
Publication title -
ieee access
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.587
H-Index - 127
ISSN - 2169-3536
DOI - 10.1109/access.2018.2815598
Subject(s) - aerospace , bioengineering , communication, networking and broadcast technologies , components, circuits, devices and systems , computing and processing , engineered materials, dielectrics and plasmas , engineering profession , fields, waves and electromagnetics , general topics for engineers , geoscience , nuclear engineering , photonics and electrooptics , power, energy and industry applications , robotics and control systems , signal processing and analysis , transportation
We consider the problem of scheduling a set of jobs subject to unequal release dates on a two-machine flow shop where the no-wait and non-availability constraints are considered so as to minimize the makespan. The contribution of this paper is two-fold. First, we propose a new mathematical formulation for the problem and derive valid inequalities. Second, we propose new lower bounds that are based on single and two-machine relaxations. These lower bounds are embedded onto a branch-and-bound algorithm enhanced by elimination and dominance rules. Computational results show that our exact methods consistently outperform the state-of-the-art branch-and-bound procedure.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom