Repository logo
HARVEST

Finance and Management Science

Permanent URI for this collection

https://hdl.handle.net/10388/8654

Browse

Browsing Finance and Management Science by Subject "mixed integer programming"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    On the exact solution of the no-wait flow shop problem with due date constraints
    (Computers & Operations Research, 2017-05) Samarghandi, Hamed; Behroozi, Mehdi
    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.