Akış tipi çizelgeleme problemi için KKE parametre eniyileme

Özet

Bu çalışma kapsamında, NP-zor tipi problem olarak bilinen permütasyon akış tipi çizelgeleme probleminin Karınca Kolonileri Eniyileme (KKE, Ant Colony Optimization-ACO) ile çözümünde kaliteli sonuçlar elde etmek üzere parametre eniyileme gerçekleştirilmiştir. Ele alınan çizelgeleme problemi, tüm makinelerde aynı sıraya sahip işlerin çizelgelenmesinden oluşur. KKE, birleşik eniyileme (combinatorial optimization) problemleri için son zamanlarda kullanılan umut verici metasezgisel bir yaklaşımdır. Burada öncelikle örnek test problemleri üzerinde denemeler yapılmış ve test edilecek uygun parametre değerleri tespit edilmiştir. Daha sonra en uygun parametreleri tespit etmek üzere iki seviyeli bir deneysel tasarım uygulanmıştır. Yapılan deneysel çalışmalar sonucunda algoritmanın performansının dikkate değer şekilde arttığı gözlenmiştir.

Abstract

In this study, parameter tuning is performed to improve the solution of Ant Colony Optimization (ACO) of permutation flow shop scheduling problem, which is known as NP-hard type. The permutation flow shop scheduling problem consists of scheduling jobs with the same order of entry at all machinery. The job can be processed at most on one machine; meanwhile one machine can process at most one job. Ant colony optimization is one of the most recent and promising metaheuristics for combinatorial optimization problems. Similar to other heuristics based on biological systems (such as genetic algorithms, evolutionary strategies, artificial neural network, artificial immune systems) ant algorithms have been inspired by the behavior of real ant colonies. In the ant colony optimization metaheuristic, a colony of artificial ants cooperate in finding good solutions to optimization problems. Here, in order to determine the tendency for the value of ACO parameters, first sample experiments are designed and accordingly appropriate values are determined. Later, experiments are extended to fine-tune of the parameters. A two-level experimental design is used for fine-tuning of parameters. During this study, a total of 3350 runs is carried on 30 test problems with 5, 10 and 20 machines and 20 jobs for makespan objectives. As a result of these experimental studies, a noticeable performance increase was observed.