Single machine scheduling with sequence dependent setup times

Abstract

In this thesis, we study a single machine scheduling problem with sequence dependent setup times where the jobs are processed in shifts with constant length. There is a certain amount of time between each pair of consecutive shifts for periodic mainte nance, the machine does not work in maintenance but this time can also be used for the setup. Our goal is to complete the jobs in minimum amount of time. The setting considered in this thesis has applications in different industries including beverage and chemical industries. The problem can be solved with a small number of jobs by using some mathe matical models in computer environment. However, as the number of jobs increases, the difficulty of solving the problem increases exponentially. In order to overcome the problem, we proposed heuristic algorithms, and they provided us to find good solutions for the problem. The new heuristic algorithm is based on the First Fit Algorithm (FF) that is used for solution of bin packing problems. Firstly, First Fit Decreasing (FFD) Algorithm has been applied to the problem, and jobs were assigned to shifts. For each shift in the result of FFD algorithm, used setup times were reduced by changing the orders of jobs in shift. The gaps occurred in some shifts with decrease in setup time used. All shifts were combined to fill in the gaps and FF algorithm was run. This process was repeated until there is no more improvement to be achieved for completion time of last job. This algorithm was named as Improved First Fit Heuristic (IFFH) algorithm. Then, according the result of IFFH algorithm, binary combinations of shifts and last shift were concatenated. The IFFH algorithm was repeated three times for the triple combinations of shifts. The minimum completion time was accepted as a solution. This algorithm was named as Improved First Fit Heuristic-2 (IFFH-2) algorithm. Consequently, the algorithms were compared with benchmarks in the literature.

Bu tezde, i¸slerin sabit uzunlu˘ga sahip vardiyalarda yapıldı˘gı, sıraya ba˘glı hazırlık s¨urelerine sahip tekli makine ¸cizelgeleme problemini inceliyoruz. Her ardı¸sık vardiya ¸cifti arasında periyodik bakıma ayrılmı¸s belirli bir s¨ure vardır, makine bu s¨ure i¸cerisinde ¸calı¸smaz ancak bu s¨ure hazırlık s¨uresi olarak kullanılabilir. Amacımız t¨um i¸sleri min imum s¨urede tamamlamaktır. Bu tezde ele alınan ortam, i¸cecek ve kimya end¨ustrileri dahil olmak ¨uzere farklı end¨ustrilerde uygulamalara sahiptir. Problem az sayıda i¸s i¸cin bilgisayar ortamında bazı matematiksel modeller kul lanılarak ¸c¨oz¨ulebilir. Ancak i¸s sayısı arttık¸ca problemi ¸c¨ozme zorlu˘gu da katlanarak artmaktadır. Biz bu problemin ¨ustesinden gelmek i¸cin bazı sezgisel algoritmalar ¨onerdik, ve ¨onerdi˘gimiz algoritmalar probleme iyi ¸c¨oz¨umler bulmamızı sa˘gladı. Yeni sezgisel algoritmalar, kutulama problemlerinin ¸c¨oz¨um¨u i¸cin kullanılan ˙Ilk Sı˘gan Al goritmasına dayanmaktadır. Oncelikle probleme ¨ ˙Ilk Sı˘gan Azalan Algoritması uygulandı ve i¸sler vardiyalara atandı. ˙Ilk sı˘gan azalan algoritmasının sonu¸clarındaki her vardiya i¸cin, vardiyadaki i¸slerin sıraları de˘gi¸stirilerek kullanılan hazırlık s¨ureleri azaltıldı. Kullanılan hazırlık s¨urelerinin azalmasıyla birlikte vardiyada bo¸sluklar olu¸stu. Bo¸slukları doldurmak i¸cin t¨um vardiyalar birle¸stirildi ve ilk sı˘gan algoritması ¸calı¸stırıldı. Bu s¨ure¸c, son i¸sin tamamlanma s¨uresi i¸cin daha fazla iyile¸sme sa˘glanmayana kadar tekrar edildi. Bu algoritma, Geli¸stirilmi¸s ˙Ilk Sı˘gan Sezgisel algoritması olarak adlandırıldı. Daha sonra, Geli¸stirilmi¸s ˙Ilk Sı˘gan Sezgisel algoritmasının sonucuna g¨ore, son vardiya hari¸c vardiyaların ikili kombinasyonları ile son vardiya birle¸stirildi. Geli¸stirilmi¸s ˙Ilk Sı˘gan Sezgisel Algoritması, ¨u¸cl¨u vardiya kombinasyonları i¸cin ¨u¸c kez tekrarlandı. Minimum tamamlanma s¨uresi ¸c¨oz¨um olarak kabul edildi. Bu algoritma, Geli¸stirilmi¸s ˙Ilk Sı˘gan Sezgisel Algoritması-2 olarak adlandırıldı. Onerilen algoritmalar literat¨urdeki benzer ¨ ¨orneklerle kar¸sıla¸stırıldı.