An exact extended formulation for the unrelated parallel machine total weighted completion time problem

Bülbül, Kerem and Şen, Halil (2017) An exact extended formulation for the unrelated parallel machine total weighted completion time problem. Journal of Scheduling, 20 (4). pp. 373-389. ISSN 1094-6136 (Print) 1099-1425 (Online)

This is the latest version of this item.

[thumbnail of This is a RoMEO green journal -- author can archive pre-print (ie pre-refereeing)] PDF (This is a RoMEO green journal -- author can archive pre-print (ie pre-refereeing))
RmTWCT_rev1.pdf

Download (391kB)

Abstract

The plethora of research on NP-hard parallel machine scheduling problems is focused on heuristics due to the theoretically and practically challenging nature of these problems. Only a handful of exact approaches are available in the literature, and most of these suffer from scalability issues. Moreover, the majority of the papers on the subject are restricted to the identical parallel machine scheduling environment. In this context, the main contribution of this work is to recognize and prove that a particular preemptive relaxation for the problem of minimizing the total weighted completion time (TWCT) on a set of unrelated parallel machines naturally admits a non-preemptive optimal solution and gives rise to an exact mixed integer linear programming formulation of the problem. Furthermore, we exploit the structural properties of TWCT and attain a very fast and scalable exact Benders decomposition-based algorithm for solving this formulation. Computationally, our approach holds great promise and may even be embedded into iterative algorithms for more complex shop scheduling problems as instances with up to 1000 jobs and 8 machines are solved to optimality within a few seconds.
Item Type: Article
Uncontrolled Keywords: unrelated parallel machines; weighted completion time; Benders decomposition; cut strengthening; exact method; preemptive relaxation; transportation problem
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: Kerem Bülbül
Date Deposited: 09 Sep 2017 12:38
Last Modified: 09 Sep 2017 12:38
URI: https://research.sabanciuniv.edu/id/eprint/32883

Available Versions of this Item

Actions (login required)

View Item
View Item