Scheduling in a three-stage dedicated hybrid flowshop with a common third-stage

Abstract

Bu çalışmada, birincisinin üçüncü aşaması ile ikincisinin ikinci aşaması ortak olan iki imalat hattını barındıran bir imalat ortamının çizelgelenmesi problemi ele alınmıştır. Birinci imalat hattının her aşamasında tek makine mevcut iken, ikinci imalat hattının ilk aşamasında iki tane özdeş parallel makine yer almaktadır. Birinci tür işler ilk imalat hattında işlenirken ikinci imalat hattı ikinci tip işlere tahsis edilmiştir. Her iki tür işin son operasyonu ortak makinada işlenmek durumundadır. Problemimiz, bütün işlerin iki imalat hattının tüm aşamalarındaki sıra ve çizelgelerini belirlemek ve böylelikle başlangıç ve bitiş arasında geçen süreyi en aza indirmektir. Problemin optimal çözümünü bulmak için bir matematiksel model ile alt ve üst sınır işlemleriyle birlikle bir dal-sınır algoritması geliştirilmiştir; kesin çözümün elde edilemediği durumlarda, makul bir hesaplama uğraşıyla iyi çözümler sağlamak üzere sezgisel algoritmalar önerilmiştir. Çözüm yaklaşımlarımızın etkinliği sayısal analizlerle ispat edilmiştir.Anahtar Kelimeler: Karma Akış Tipi Atölye Çizelgelemesi, Tahsisli Makine, Matematiksel Model, Dal-Sınır Algoritması.

In this study, we consider a scheduling problem of a manufacturing environment in which there are two manufacturing flow lines, where the third stage of the first line and the second stage of the second line are common. Each stage in the first flow line has a single machine whereas the second flow line contains two identical parallel machines in its first stage. Type-1 jobs are processed in the first flow line, whereas second flow line is dedicated to type-2 jobs. The last operation, of both types of jobs, must be processed on a common machine. The problem is to determine the sequence and schedule of all jobs at all stages of the two flow lines so that the makespan is minimized. We develop a mathematical model and a branch-and-bound algorithm with lower and upper bounding procedures to find optimal solution; we propose heuristic algorithms which provide good quality solutions at little computational effort when the computational effort to obtain an exact solution is prohibitive. The effectiveness of our solution approaches are demonstrated by computational analyses.Keywords: Hybrid Flowshop Scheduling, Dedicated Machine, Mathematical Model, Branch-and-bound Algorithm.