Stokastik İlişkisiz Paralel Makine Çizelgeleme Problemi için bir Matematiksel Model
A Mathematical Model for Stochastic Unrelated Parallel Machine Scheduling Problem
Yazar: Ertem, Mehmet; Özçelik, Feriştah; Saraç, Tuğba
Dergi: Avrupa Bilim ve Teknoloji Dergisi No. 29, 2021
Anahtar kelimeler: Engineering ; Mühendislik ; Unrelated parallel machine scheduling problem,Two-stage stochastic programming,stochastic sequence-dependent setup times. ; İlişkisiz parallel makina çizelgeleme problemi,İki aşamalı stokastik programlama,stokastik sıra bağımlı hazırlık süreleri

Bir iş, aynı işlemi yapabilen makinaların herhangi birisinde işlem görebiliyor ise bu makinalar, paralel makinalar olarak adlandırılmaktadır. Eğer paralel makinaların bir iş için işlem süreleri farklılık gösteriyorsa bu makinalar ilişkisizdir. İlişkisiz paralel makine çizelgeleme problemi (UPM) hem endüstride yaygın bir uygulama alanına sahip olması hemde esnek atölye tipi çizelgeleme problemi gibi daha karmaşık problemlerin alt problemi olması nedeniyle çizelgeleme literatüründe önemli bir yere sahiptir. Problemin işlem süreleri, hazırlık süreleri, müşteri terminleri gibi parametrelerinin değerlerini kesin olarak belirlemek zordur. Bu parametreler taleplerin ve termin tarihlerinin müşteri tarafından son anda değiştirilmesi, makine arızaları, hammadde temininde aksamalar gibi pek çok faktöre bağlı olarak değişkenlik gösterebilmektedir. UPM doğası gereği stokastik bir yapıya sahiptir ve nedenle literatürde problemi deterministik olarak ele alan çok sayıda çalışmanın yanısıra stokastik olarak ele alan çalışmalar da mevcuttur. Ancak problemi stokastik olarak ele alan çalışmaların çoğu işlem sürelerinin stokastik olması durumunu incelemişlerdir. Bu çalışmada ise literatürün genelinden farklı olarak sıra bağımlı hazırlık sürelerini stokastik olarak ele almanın katkısı araştırılmıştır. Sıra bağımlı hazırlık süreli stokastik UPM için iki aşamalı stokastik programlama yaklaşımı kullanılmıştır. Stokastik problem için bir matematiksel model önerilmiştir. Önerilen modelin etkinliği rassal türetilen test problemleri üzerinde gösterilmiştir. Öncelikle tüm test problemleri parametrelerin deterministik olduğu varsayımı ile deterministik model ile çözülmüş ve çizelgeler elde edilmiştir. Daha sonra sıra bağımlı hazırlık süreleri stokastik olarak ele alınmış ve problemler önerilen stokastik model ile çözülmüştür. Son olarak her bir problem için sıra bağımlı hazırlık süresini stokastik ele almanın katkısı hesaplanmıştır. Yapılan testler, sadece 10 işin olduğu küçük boyutlu problemler için bile problemi stokastik olarak ele almanın son işin tamamlanma zamanını ortalama yüzde %0,305 kısalttığını ortaya koymuştur.

If a job can be processed by any machines that can do the same operation, these machines are called parallel machines. If parallel machines have different processing times for a job, these machines are unrelated. The unrelated parallel machine scheduling problem (UPM) has an important place in the scheduling literature because it has a wide application area in the industry, and it is a sub-problem of more complex problems such as flexible job-shop scheduling problem. It is difficult to precisely determine the values of the parameters of the problem, such as processing times, setup times, due dates. These parameters may vary depending on many factors, such as changes in demands and due dates by the customer at the last moment, machine malfunctions, and disruptions in raw material supply. For this reason, UPM has a stochastic structure by nature, and there are many studies in the literature that deal with the problem as deterministic, as well as studies that deal with it as stochastic. However, most of the studies dealing with the problem as stochastic have examined the case of stochastic processing times. In this study, unlike the general literature, the contribution of handling the sequence-dependent setup times as stochastic was investigated. A two-stage stochastic programming approach is used for stochastic UPM with sequence-dependent setup time. A mathematical model is proposed for the stochastic problem. The effectiveness of the proposed model is demonstrated on randomly generated test problems. First of all, all test problems were solved with a deterministic model, assuming that the parameters were deterministic, and schedules were obtained. Then, the sequence-dependent setup times were handled stochastic, and the problems were solved with the proposed stochastic model. Finally, the contribution of stochastic handling of the sequence-dependent setup time for each problem is calculated. Tests have revealed that even for small-sized problems with only 10 jobs, treating the problem as stochastic shortens the completion time of the last job by an average of 0.305%.