Assignment and scheduling problem in identical parallel machines

Abstract

Bu çalışmada ele alınan problem, üretim süreçleri tamamlanmış çeşitli boya tiplerinin, istenilen ambalajlarla eşlenerek, dolum makinalarında çizelgelenmesidir. DYO dolum ünitesinde işlem süreleri birbirinden farklı üç makina grubu bulunmaktadır; otomatik, yarı otomatik ve manuel. Her bir makina grubu ise farklı sayılarda özdeş makinalardan oluşmaktadır. Bu nedenle, problem iki aşamalı olarak ele alınmıştır; işlerin, dolum makinesi gruplarına atanması ve akabinde atama yapılan grup içerisindeki paralel makinalarda çizelgelenmesi.Problemi çözmek için, genelleştirilmiş atama problemine gömülen genel değişken komşuluk arama (gDKA) algoritması geliştirilmiştir. Algoritma iki ana kısımdan oluşmaktadır. İlk kısımda, makina gruplarına işlerin atanması DKA algoritması ile ikinci kısımda (iç döngüde) ise, iş kümelerinin paralel makinalarda çizelgelenmesi gene DKA algoritmasına dayanan liste çizelgeleme yöntemi ile yapılmıştır. Ayrıca aynı problemi çözmek için ayrık yapay arı kolonisi algoritması ve genetik algoritma geliştirilmiştir.

This paper presents a discrete artificial bee colony algorithm to solve the assignment and scheduling problem in DYO painting company. In the DYO Paint Company, there are three types of filling machines groups: automatic, semiautomatic and manual. In each group, there are several numbers of identical machines. The problem is to first assign these filling production orders to machine groups. Then, these filling production orders on each machine groups should be scheduled on identical parallel machines to minimize the sum of makespan and total tardiness. We also develop a traditional genetic algorithm and variable neighborhood search algorithm to solve the same problem. The computational results show that the VNS algorithm slightly outperforms the GA and DABC on set of benchmark problems we generated.