Dominance rules for three-machine flow-shop scheduling problem with unit processing times, release times and chain precedence relationships

Abstract

Akış tipi işlik problemleri, işlerin belirli bir sırayla makineleri ziyaret etmeleri gerekençizelgeleme problemleridir.Bu tez üç makineli, birim işlem süreli, başlangıç zamanlı, zincir yapılıöncüllük kısıtları olan akış tipi işliklerin enbüyük geç kalma süresini enküçültmeyi amaçlayan problemle ilgilidir.Her iş her makineda bir birim işlemgörmektedir. İşler verilen başlangıç zamanlarından önce işlemebaşlayamaz. Her iş en fazla bir öncül vebir ardıl işe sahip olabilir ve işler öncüllerinin bütün işlemleribitmeden işleme başlayamaz. Problemi çözenkişinin amacı ise bütün işleri bitiş tarihlerine kadar tamamlamak,eğer gecikme olursa da bütün işler içerisindeen fazla gecikenin gecikmesini en az hale getirmektir.Bu problem hesaplama karmaşıklığı bakımından henüzsınıflandırılmamıştır.Bu tezde yukarıdaki akış tipi işlik çizelgeleme problemi için polinomzamanlı bir algoritma geliştirilmesi amaçlanmıştır.Problemin iki makineli benzeri ile ilişki kurularak olurlu çizelgelerinbazı özellikleri belirlenmiştir. Yoğun zaman aralıklarıincelenerek problemin başlangıç zamanları ve bitiş zamanlarıolurlu çizelge dışlamayacak şekilde daraltılmıştır ve bahsigeçen olurlu çizelge özellikleri polinom zamanlı algoritmalarlasağlanmıştır. Çözüm için yeterli şartlar ispatlanmış ve buşartları sağlayacak değişiklikleri yapması için polinom zamanlıbir algoritma ispatsız bir şekilde önerilmiştir.

A flow-shop problem is a scheduling problem where every job consists of afixed number of operations each of which to be processed on a differentmachine. The operations of each job have to be processed in a fixed order,in other words every job visits the machines in the same order.The problem of concern in this thesis is the three-machineflow-shop scheduling problem with unit processing times, release timesand chain precedence relationships. All jobs have to spend unit time oneach machine. The jobs are available to be initiated at their releasetimes. A partial order of jobs that allows at most one successor andone predecessor for each job restricts the starting times so thatevery job can be initiated after its predecessor is completed. Ourobjective is to construct a schedule that will minimize the maximumlateness. The problem is currently open with respect to complexityclassification.In this thesis a polynomial algorithm to minimize the maximum latenessis sought for the above flow-shop scheduling problem with unitprocessing times, release times and chain precedence relationships.Several dominance rules for a feasible schedule are establishedthrough the correspondence with the two-machine version of theproblem. By considering overloaded time intervals, given set ofdeadlines and release times are modified to find an equivalent problemwith the same set of solutions. Further dominance rules arepresented and shown to be achievable in polynomial time. Sufficientconditions for the solution are proved and a polynomial time limitedbacktracking algorithm exploiting the above mentioned dominancerules is suggested for the problem without precise proof ofcompleteness.