On the exact solution of the no-wait flow shop problem with due date constraints
Date
2017-05
Authors
Samarghandi, Hamed
Behroozi, Mehdi
Journal Title
Journal ISSN
Volume Title
Publisher
Computers & Operations Research
ORCID
Type
Article
Degree Level
Abstract
This 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.
Description
Keywords
No-wait flow shop, due date constraints, mixed integer programming, constraint programming, enumeration algorithm
Citation
Samarghandi, 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.013
Degree
Department
Program
Advisor
Committee
Citation
Samarghandi, 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.013