Minimizing the Makespan for Unrelated Parallel Machines
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.
Makespan, unrelated parallel machines, simulated annealing, tabu search, squeaky wheel optimization
Operations and Supply Chain Management
International Journal of Artificial Intelligence Tools
GUO, Yunsong; LIM, Andrew; RODRIGUES, Brian; and YANG, Liang.
Minimizing the Makespan for Unrelated Parallel Machines. (2007). International Journal of Artificial Intelligence Tools. 16, (3), 399-415. Research Collection Lee Kong Chian School Of Business.
Available at: http://ink.library.smu.edu.sg/lkcsb_research/556