Minimizing the Makespan for Unrelated Parallel Machines

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 th...

Full description

Saved in:
Bibliographic Details
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
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
Description
Summary: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.

Similar Items