A Strong Preemptive Relaxation for Weighted Tardiness and Earliness/Tardiness Problems on Unrelated Parallel Machines

Research on due date-oriented objectives in the parallel machine environment is at best scarce compared to objectives such as minimizing the makespan or the completion time-related performance measures. Moreover, almost all existing work in this area is focused on the identical parallel machine envi...

Full description

Saved in:
Bibliographic Details
Published in:INFORMS journal on computing 2015-01, Vol.27 (1), p.135-150
Main Authors: Sen, Halil, Bulbul, Kerem
Format: Article
Language:English
Subjects:
Algorithms
Benders decomposition
Decomposition (Mathematics)
heuristic
lower bound
Mathematical optimization
Methods
preemptive relaxation
Production engineering research
Relaxation methods (Mathematics)
Scheduling (Management)
transportation problem
unrelated parallel machines
weighted earliness and tardiness
weighted tardiness
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Research on due date-oriented objectives in the parallel machine environment is at best scarce compared to objectives such as minimizing the makespan or the completion time-related performance measures. Moreover, almost all existing work in this area is focused on the identical parallel machine environment. In this study, we leverage on our previous work on the single machine total weighted tardiness (TWT) and total weighted earliness/tardiness (TWET) problems and develop a new preemptive relaxation for both problems on a bank of unrelated parallel machines. The key contribution of this paper is devising a computationally effective Benders decomposition algorithm to solve the preemptive relaxation formulated as a mixed-integer linear program. The optimal solution of the preemptive relaxation provides a tight lower bound. Moreover, it offers a near-optimal partition of the jobs to the machines. We then exploit recent advances in solving the nonpreemptive single-machine TWT and TWET problems for constructing nonpreemptive solutions of high quality to the original problem. We demonstrate the effectiveness of our approach with instances of up to five machines and 200 jobs.
ISSN:1091-9856
1526-5528
DOI:10.1287/ijoc.2014.0615