A Computational Study of the Two-Machine No-Wait Flow Shop Scheduling Problem Subject to Unequal Release Dates and Non-Availability Constraints
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 formulati...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2018-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8315022/ |
| _version_ | 1818410483717242880 |
|---|---|
| author | Mohamed Labidi Anis Kooli Talel Ladhari Anis Gharbi Umar S. Suryahatmaja |
| author_facet | Mohamed Labidi Anis Kooli Talel Ladhari Anis Gharbi Umar S. Suryahatmaja |
| author_sort | Mohamed Labidi |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-14T10:16:14Z |
| format | Article |
| id | doaj.art-30906c5a29634166813acdda1897f386 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-14T10:16:14Z |
| publishDate | 2018-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-30906c5a29634166813acdda1897f3862022-12-21T23:06:49ZengIEEEIEEE Access2169-35362018-01-016162941630410.1109/ACCESS.2018.28155988315022A Computational Study of the Two-Machine No-Wait Flow Shop Scheduling Problem Subject to Unequal Release Dates and Non-Availability ConstraintsMohamed Labidi0https://orcid.org/0000-0002-9585-1339Anis Kooli1Talel Ladhari2Anis Gharbi3Umar S. Suryahatmaja4Department of Industrial Engineering, College of Engineering, King Saud University, Riyadh, Saudi ArabiaEcole Supérieure des Sciences Economiques et Commerciales de Tunis, Université de Tunis, Tunis, TunisiaEcole Supérieure des Sciences Economiques et Commerciales de Tunis, Université de Tunis, Tunis, TunisiaDepartment of Industrial Engineering, College of Engineering, King Saud University, Riyadh, Saudi ArabiaDepartment of Industrial Engineering, College of Engineering, King Saud University, Riyadh, Saudi ArabiaWe 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.https://ieeexplore.ieee.org/document/8315022/Schedulingflow shopno-waitnon-availabilitylower boundsbranch-and-bound algorithm |
| spellingShingle | Mohamed Labidi Anis Kooli Talel Ladhari Anis Gharbi Umar S. Suryahatmaja A Computational Study of the Two-Machine No-Wait Flow Shop Scheduling Problem Subject to Unequal Release Dates and Non-Availability Constraints IEEE Access Scheduling flow shop no-wait non-availability lower bounds branch-and-bound algorithm |
| title | A Computational Study of the Two-Machine No-Wait Flow Shop Scheduling Problem Subject to Unequal Release Dates and Non-Availability Constraints |
| title_full | A Computational Study of the Two-Machine No-Wait Flow Shop Scheduling Problem Subject to Unequal Release Dates and Non-Availability Constraints |
| title_fullStr | A Computational Study of the Two-Machine No-Wait Flow Shop Scheduling Problem Subject to Unequal Release Dates and Non-Availability Constraints |
| title_full_unstemmed | A Computational Study of the Two-Machine No-Wait Flow Shop Scheduling Problem Subject to Unequal Release Dates and Non-Availability Constraints |
| title_short | A Computational Study of the Two-Machine No-Wait Flow Shop Scheduling Problem Subject to Unequal Release Dates and Non-Availability Constraints |
| title_sort | computational study of the two machine no wait flow shop scheduling problem subject to unequal release dates and non availability constraints |
| topic | Scheduling flow shop no-wait non-availability lower bounds branch-and-bound algorithm |
| url | https://ieeexplore.ieee.org/document/8315022/ |
| work_keys_str_mv | AT mohamedlabidi acomputationalstudyofthetwomachinenowaitflowshopschedulingproblemsubjecttounequalreleasedatesandnonavailabilityconstraints AT aniskooli acomputationalstudyofthetwomachinenowaitflowshopschedulingproblemsubjecttounequalreleasedatesandnonavailabilityconstraints AT talelladhari acomputationalstudyofthetwomachinenowaitflowshopschedulingproblemsubjecttounequalreleasedatesandnonavailabilityconstraints AT anisgharbi acomputationalstudyofthetwomachinenowaitflowshopschedulingproblemsubjecttounequalreleasedatesandnonavailabilityconstraints AT umarssuryahatmaja acomputationalstudyofthetwomachinenowaitflowshopschedulingproblemsubjecttounequalreleasedatesandnonavailabilityconstraints AT mohamedlabidi computationalstudyofthetwomachinenowaitflowshopschedulingproblemsubjecttounequalreleasedatesandnonavailabilityconstraints AT aniskooli computationalstudyofthetwomachinenowaitflowshopschedulingproblemsubjecttounequalreleasedatesandnonavailabilityconstraints AT talelladhari computationalstudyofthetwomachinenowaitflowshopschedulingproblemsubjecttounequalreleasedatesandnonavailabilityconstraints AT anisgharbi computationalstudyofthetwomachinenowaitflowshopschedulingproblemsubjecttounequalreleasedatesandnonavailabilityconstraints AT umarssuryahatmaja computationalstudyofthetwomachinenowaitflowshopschedulingproblemsubjecttounequalreleasedatesandnonavailabilityconstraints |