Repository logo
HARVEST
 

On the exact solution of the no-wait flow shop problem with due date constraints

Simple item page
dc.contributor.authorSamarghandi, Hamed
dc.contributor.authorBehroozi, Mehdi
dc.date.accessioned2018-11-07T16:11:58Z
dc.date.available2018-11-07T16:11:58Z
dc.date.issued2017-05
dc.description.abstractThis paper deals with the no-wait flow shop scheduling problem with due date constraints. In the no-wait flow shop problem, waiting time is not allowed between successive operations of jobs. Moreover, the jobs should be completed before their respective due dates; due date constraints are dealt with as hard constraints. The considered performance criterion is makespan. The problem is strongly NP-hard. This paper develops a number of distinct mathematical models for the problem based on different decision variables. Namely, a mixed integer programming model, two quadratic mixed integer programming models, and two constraint programming models are developed. Moreover, a novel graph representation is developed for the problem. This new modeling technique facilitates the investigation of some of the important characteristics of the problem; this results in a number of propositions to rule out a large number of infeasible solutions from the set of all possible permutations. Afterward, the new graph representation and the resulting propositions are incorporated into a new exact algorithm to solve the problem to optimality. To investigate the performance of the mathematical models and to compare them with the developed exact algorithm, a number of test problems are solved and the results are reported. Computational results demonstrate that the developed algorithm is significantly faster than the mathematical models.en_US
dc.description.versionPeer Revieweden_US
dc.identifier.citationSamarghandi, H., & Behroozi, M. (2017). On the exact solution of the no-wait flow shop problem with due date constraints, Computers & Operations Research, 81: p. 141-159. https://doi.org/10.1016/j.cor.2016.12.013en_US
dc.identifier.urihttp://hdl.handle.net/10388/11495
dc.language.isoenen_US
dc.publisherComputers & Operations Researchen_US
dc.subjectNo-wait flow shopen_US
dc.subjectdue date constraintsen_US
dc.subjectmixed integer programmingen_US
dc.subjectconstraint programmingen_US
dc.subjectenumeration algorithmen_US
dc.titleOn the exact solution of the no-wait flow shop problem with due date constraintsen_US
dc.typeArticleen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
NWFS+DD - Exact - Post Print.pdf
Size:
1.87 MB
Format:
Adobe Portable Document Format
Description:
Main article
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.28 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Finance and Management Science