Publication: An ant colony optimization approach for the proportionate multiprocessor open shop
Abstract
Atölye çizelgeleme problemleri imalat ve hizmet sektörlerinin her birinde son derece geniş uygulama alanlarına sahiptir. Esnek açık atölye tipi çizelgeleme yaygın görülen atölye ortamları arasındadır. Birden fazla işlem istasyonu içeren bu atölye tipinde bu istasyonlardan en az biri aynı işlemi yapan paralel tezgahlara sahiptir. Bu işlem istasyonlarında tamamlanması gereken n tane iş bulunur ve işlerin istasyonları ziyaret etmede uymaları gereken bir rota kısıtı yoktur. Bu atölye tipi özellikle tıbbi teşhis test süreçlerinde, onarım ve bakım hizmetlerinde, denetim ve kalite kontrol işlemleri ve elektronik üretim süreçlerinde yaygın olarak bulunmaktadır. Ancak, bu atölye tipini çizelgeleme problemi literatürde çok az ilgi görmüştür. Son yıllarda araştırmaların sayısında artış görülmekle beraber, alan önemli ölçüde geliştirilmeye muhtaçtır. Bu tez çalışmasında, orantılı esnek açık atölye tipi ele alınmıştır. Burada orantılı ifadesi işlem istasyonlarının işlem sürelerinin her istasyon için sabit ve işten bağımsız olmasını ifade eder. Bu atölye tipini çizelgeleme problemi için bir karınca kolonisi algoritması önerilmiştir. Önerilen algoritma probleme uygun yeni ve çok etkili bir çözüm gösterimini temel alır. Algoritma ayrıca rassal arama ve yerel tarama (yerel aramaya benzer) rutinleri içerir. Geçmiş arama tecrübesinin ve probleme özel bilginin algoritmada kuvvetli ve etkin kullanımı özelleştirilmiş feremon iz bilgisi ve sezgisel bilgi yoluyla sağlanmıştır. Önerilen algoritma literatürden alınan 100 problemli bir problem seti kullanılarak test edilmiştir. Yapılan karşılaştırmalar önerilen algoritmanın bu problem tipi için literatürdeki en iyi algoritma olan dağınık arama ve yeniden yol bağlama (scatter search with path relinking) algoritmasından hem çözüm kalitesi bakımından hem de süre bakımından daha iyi olduğunu göstermiştir. Algoritmanın büyük boyutlu problemlerdeki başarısı ve bu çözüm kalitesine daha kısa sürede ulaşması bilhassa önemlidir.
Shop scheduling problems have exceptionally wide application fields both in manufacturing and service sectors. Multiprocessor open shop is among common shop environments and it consists of at least two machine centers with one or more center having parallel machines for the same task. There are n jobs to visit the centers without a predefined route. The shop widely exists particularly in diagnostic medical testing, repair and maintenance services, inspection and quality control operations and electronics manufacturing processes. However, the problem gained little attention in the literature. There has been an increase in the number of researches in the field in recent years but still there is considerable room for improvement. In this thesis study, the proportionate multiprocessor open shop problem was considered where proportionate feature refers to processing times of machine centers being fixed and independent of the job. An Ant Colony Optimization algorithm was proposed for the problem. The algorithm is based on a very efficient novel solution representation of the problem. The proposed algorithm further employs random exploration and local exploration (analogous to local search) routines. Exploitation of search knowledge and problem-specific knowledge was incorporated with tailored uses of pheromone information and heuristic information, respectively. The algorithm was tested on 100 benchmark instances from the literature. Comparisons showed that it outperformed the current state-of-the-art scatter search with path relinking algorithm both in solution quality and computational time. Of particular importance is its performance in large-scale instances and the relatively short time it required to reach the high-quality results.
Shop scheduling problems have exceptionally wide application fields both in manufacturing and service sectors. Multiprocessor open shop is among common shop environments and it consists of at least two machine centers with one or more center having parallel machines for the same task. There are n jobs to visit the centers without a predefined route. The shop widely exists particularly in diagnostic medical testing, repair and maintenance services, inspection and quality control operations and electronics manufacturing processes. However, the problem gained little attention in the literature. There has been an increase in the number of researches in the field in recent years but still there is considerable room for improvement. In this thesis study, the proportionate multiprocessor open shop problem was considered where proportionate feature refers to processing times of machine centers being fixed and independent of the job. An Ant Colony Optimization algorithm was proposed for the problem. The algorithm is based on a very efficient novel solution representation of the problem. The proposed algorithm further employs random exploration and local exploration (analogous to local search) routines. Exploitation of search knowledge and problem-specific knowledge was incorporated with tailored uses of pheromone information and heuristic information, respectively. The algorithm was tested on 100 benchmark instances from the literature. Comparisons showed that it outperformed the current state-of-the-art scatter search with path relinking algorithm both in solution quality and computational time. Of particular importance is its performance in large-scale instances and the relatively short time it required to reach the high-quality results.