Minimizing the Makespan for Unrelated Parallel Machines

Publication Type

Journal Article

Publication Date

6-2007

Abstract

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.

Keywords

Makespan, unrelated parallel machines, simulated annealing, tabu search, squeaky wheel optimization

Discipline

Operations and Supply Chain Management

Research Areas

Operations Management

Publication

International Journal of Artificial Intelligence Tools

Volume

16

Issue

3

First Page

399

Last Page

415

ISSN

0218-2130

Identifier

10.1142/S0218213007003175

Publisher

World Scientific

Additional URL

https://doi.org/10.1142/S0218213007003175

Link to Full Text

Share

COinS