59 0

A tabu search algorithm for unrelated parallel machine scheduling with sequence- and machine-dependent setups: minimizing total tardiness

Title
A tabu search algorithm for unrelated parallel machine scheduling with sequence- and machine-dependent setups: minimizing total tardiness
Author
이동호
Keywords
Scheduling; Unrelated parallel machines; Sequence- and machine-dependent setups; Total tardiness; Tabu search
Issue Date
2013-12
Publisher
Springer Science + Business Media
Citation
The International Journal of Advanced Manufacturing Technology, Vol.69, No.9-12 [2013], p2081?2089
Abstract
This study considers the problem of scheduling independent jobs on unrelated parallel machines with machine- and sequence-dependent setup times for the objective of minimizing the total tardiness, i.e., R m │S ijk │∑T j . Since the parallel machines are unrelated, sequence-dependent setup times must depend on machines. To the best of the authors’ knowledge, the simulated annealing and the iterated greedy algorithms are two existing ones for the new class of scheduling problem with an additional constraint of strict due date constraints for some jobs, i.e., deadlines. In this study, we suggest a tabu search algorithm that incorporates various neighborhood generation methods. A computational experiment was done on the instances generated by the method used in the two previous research articles, and the results show that the tabu search algorithm outperforms the simulated annealing algorithm significantly. In particular, it gave optimal solutions for more than 50 % of small-sized test instances. Also, an additional test was done to compare the performances of the tabu search and the existing iterated greedy algorithms, and the result shows that the tabu search algorithm gives quicker solutions than the iterated greedy algorithm although it gives less quality solutions.
URI
http://link.springer.com/article/10.1007/s00170-013-5192-6http://hdl.handle.net/20.500.11754/45959
ISSN
0268-3768
DOI
10.1007/s00170-013-5192-6
Appears in Collections:
COLLEGE OF ENGINEERING[S](공과대학) > INDUSTRIAL ENGINEERING(산업공학과) > Articles
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE