University of SaskatchewanHARVEST
  • Login
  • Submit Your Work
  • About
    • About HARVEST
    • Guidelines
    • Browse
      • All of HARVEST
      • Communities & Collections
      • By Issue Date
      • Authors
      • Titles
      • Subjects
      • This Collection
      • By Issue Date
      • Authors
      • Titles
      • Subjects
    • My Account
      • Login
      JavaScript is disabled for your browser. Some features of this site may not work without it.
      View Item 
      • HARVEST
      • Edwards School of Business
      • Finance and Management Science
      • View Item
      • HARVEST
      • Edwards School of Business
      • Finance and Management Science
      • View Item

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

      Thumbnail
      View/Open
      Main article (1.865Mb)
      Date
      2017-05
      Author
      Samarghandi, Hamed
      Behroozi, Mehdi
      Publisher
      Computers & Operations Research
      Type
      Article
      Peer Reviewed Status
      Peer Reviewed
      Metadata
      Show full item record
      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.
      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
      URI
      http://hdl.handle.net/10388/11495
      Subject
      No-wait flow shop
      due date constraints
      mixed integer programming
      constraint programming
      enumeration algorithm
      Collections
      • Finance and Management Science
      University of Saskatchewan

      University Library

      The University of Saskatchewan's main campus is situated on Treaty 6 Territory and the Homeland of the Métis.

      © University of Saskatchewan
      Contact Us | Disclaimer | Privacy