Cut generation based algorithms for unrelated parallel machine scheduling problems

Şen, Halil (2015) Cut generation based algorithms for unrelated parallel machine scheduling problems. [Thesis]

[thumbnail of HalilSen_10084162.pdf] PDF

Download (2MB)


Research on scheduling in the unrelated parallel machine environment is at best scarce. Moreover, almost all existing work in this area is focused on the minimization of completion time related performance measures and the solution approaches available in the literature suffer from scalability issues. In this dissertation, we leverage on the success of the mathematical programming based decomposition approaches and devise scalable, efficient, and effective cut generation based algorithms for four NP-hard unrelated parallel machine scheduling problems. In the first part,we develop a newpreemptive relaxation for the totalweighted tardiness and total weighted earliness/tardiness problems and devise a Benders decomposition algorithm for solving this preemptive relaxation formulated as a mixed integer linear program. We demonstrate the effectiveness of our approach with instances up to 5 machines and 200 jobs The second part deals with the problem of minimizing the total weighted completion time and proves that the preemptive relaxation developed in part one is an exact formulation for this problem. By exploiting the structural properties of the performance measure, we attain an exact Benders decomposition algorithm which solves instances with up to 1000 jobs and 8 machines to optimality within a few seconds. In the last part, we tackle the unrestricted common due date just-in-time scheduling problemand develop a logic-based Benders decomposition algorithm. Aside from offering the best solution approach for this problem, we demonstrate that it is possible to devise scalable logic-based algorithms for scheduling problems with irregular minsum objectives.
Item Type: Thesis
Additional Information: Yükseköğretim Kurulu Tez Merkezi Tez No: 420263.
Uncontrolled Keywords: Unrelated parallel machine scheduling. -- Benders decomposition. -- Logic-based Benders decomposition. -- Exact method. -- Heuristics. -- Alakasız paralel makine çizelgeleme. -- Benders ayrıştırma. -- Mantık tabanlı Benders ayrıştırma. -- Pekin yöntem. -- Sezgizel yöntem.
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 09 Apr 2018 11:07
Last Modified: 26 Apr 2022 10:15

Actions (login required)

View Item
View Item