TY - GEN
T1 - Machine scheduling with sequence-dependent setup times using a randomized search heuristic
AU - Jairo, R. Montoya Torres
AU - Milton, Soto Ferrari
AU - Fernando, González Solano
AU - Edgar, H. Alfonso Lizarazo
PY - 2009
Y1 - 2009
N2 - This paper considers the problem of scheduling a set of jobs on both asingle machine and identical parallel machines with the objective of minimizingthe makespan or maximum completion time of all jobs. Jobs are subject to releasedates and there are sequence-dependent setup times. Since this problem is knownto be strongly NP-hard even for the single machine case, this paper proposes aheuristic algorithm to solve it. The algorithm uses a strategy of randomgeneration of various execution sequences, and then selects the best of suchschedules. Experiments are performed using random-generated data. Results showthat the heuristic performs very well compared against the optimal solution, andrequiring short computational time.
AB - This paper considers the problem of scheduling a set of jobs on both asingle machine and identical parallel machines with the objective of minimizingthe makespan or maximum completion time of all jobs. Jobs are subject to releasedates and there are sequence-dependent setup times. Since this problem is knownto be strongly NP-hard even for the single machine case, this paper proposes aheuristic algorithm to solve it. The algorithm uses a strategy of randomgeneration of various execution sequences, and then selects the best of suchschedules. Experiments are performed using random-generated data. Results showthat the heuristic performs very well compared against the optimal solution, andrequiring short computational time.
KW - Heuristic
KW - Parallel machines
KW - Scheduling
KW - Setup times
KW - Single machine
UR - https://www.scopus.com/pages/publications/77956122302
M3 - Contribution to conference proceedings
AN - SCOPUS:77956122302
SN - 9781424441365
T3 - 2009 International Conference on Computers and Industrial Engineering, CIE 2009
SP - 28
EP - 33
BT - 2009 International Conference on Computers and Industrial Engineering, CIE 2009
PB - IEEE Computer Society
T2 - 2009 International Conference on Computers and Industrial Engineering, CIE 2009
Y2 - 6 July 2009 through 9 July 2009
ER -