A New Crossover Operator for Single Machine Total Weighted Tardiness Problem with Sequence Dependent Setup Times

Gökhan KIRLIK; Zuhal KARTAL; Servet HASGUL

Makale detayları

A New Crossover Operator for Single Machine Total Weighted Tardiness Problem with Sequence Dependent Setup Times

Yazarlar:

Gökhan KIRLIK | Zuhal KARTAL | Servet HASGUL

Yayıncı:

Gazi University

Dergi:

Gazi University Journal of Science 2012 Vol.25 Issue 1, pp.127-136

Belge Tipi:

Makale

Yayın Tarihi:

1/2012

Belge Dili:

İngilizce

Document ID (Org No.):

2000429467

eISSN:

2147-1762

Özet:

 


The single machine total weighted tardiness problem with sequence dependent setup times is a challenging and heavily studied problem. This problem is NP-hard, so several heuristics have been proposed in the literature so far. One of them is the genetic algorithm. The genetic algorithm is both powerful solution technique and applicable to wide range of different problem types, although its performance is heavily parameter and operator dependent. It is seen in literature that the well-conducted and adapted genetic algorithm operators and parameters increase the solution quality. In this study, a new crossover operator is proposed for the single machine with sequence dependent setup times problem to minimize the total weighted tardiness. The proposed crossover operator improves the relative positions by using apparent tardiness cost with setups (ATCS) heuristic while preserving the absolute positions. These are the two main aspects of the permutation type crossover operators for scheduling problems. The performance of the proposed crossover operator is tested by comparing it with partially mapped crossover (PMX) in different test cases using benchmark instances from literature. It is shown that the proposed ATCS based crossover operator gives better results than PMX in all test problems.

Key Words: Weighted tardiness scheduling, Sequence dependent setups, Genetic algorithm, Crossover operator

 

.

Makale detayları

A New Crossover Operator for Single Machine Total Weighted Tardiness Problem with Sequence Dependent Setup Times

Yazarlar: Gökhan KIRLIK | Zuhal KARTAL | Servet HASGUL

Yayıncı: Gazi University

Dergi: Gazi University Journal of Science 2012 Vol.25 Issue 1, pp.127-136

Belge Tipi: Makale

Yayın Tarihi: 1/2012

Belge Dili: İngilizce

Document ID (Org No.): 2000429467

eISSN: 2147-1762

Sayı

Yazarlar:

Gökhan KIRLIK | Zuhal KARTAL | Servet HASGUL

Yayıncı:

Gazi University

Dergi:

Gazi University Journal of Science 2012 Vol.25 Issue 1, pp.127-136

Belge Tipi:

Makale

Yayın Tarihi:

1/2012

Belge Dili:

İngilizce

Document ID (Org No.):

2000429467

eISSN:

2147-1762