Minimizing the Makespan for Unrelated Parallel Machines

• Main Authors: GUO, Yunsong, LIM, Andrew, RODRIGUES, Brian, YANG, Liang
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2007
• Subjects: Makespan; unrelated parallel machines; simulated annealing; tabu search; squeaky wheel optimization; Operations and Supply Chain Management
• Online Access: https://ink.library.smu.edu.sg/lkcsb_research/556; https://doi.org/10.1142/S0218213007003175
• Institution: Singapore Management University

In this paper, we study the unrelated parallel machine problem for minimizing the makespan, which is NP-hard. We used Simulated Annealing (SA) and Tabu Search (TS) with Neighborhood Search (NS) based on the structure of the problem. We also used a modified SA algorithm, which gives better results than the traditional SA and developed an effective heuristic for the problem: Squeaky Wheel Optimization (SWO) hybrid with TS. Experimental results average 2.52% from the lower bound and are within acceptable timescales improving current best results for the problem.