Nonidentical parallel machine scheduling with time-dependent deterioration of jobs

Abstract

We consider scheduling of deteriorating jobs on nonidentical parallel machines where the objective is to minimize mean flow time while ensuring the average value (i.e., quality) of processed jobs on machines exceeds a threshold. Deterioration is considered to be time-dependent and has a two-fold effect on jobs. The processing time of jobs as well as their values are deteriorating with time. We analyze the scheduling problem where the processing time and the value functions take linear (piece-wise linear) forms. We first formulate the problem as a mixed integer linear program and obtain optimal solutions for limited problem sizes. We then develop a heuristic algorithm to solve the problem and several ideas to sort jobs in the system. Linear and poisson regression models are trained to predict position of jobs on machines and also used in rank aggregation with simple sorting lists to provide better sorting approaches.

Bu tez çalışmasında, özdeş olmayan paralel makinelere atanmış zamana duyarlı işlerin ortalama kalitesinin bir eşiği aşması sağlanırken, tüm işlerin ortalama akış süresini en aza indirmeyi amaçlayan bir çizelgeleme sorunu üzerine odaklanılmıştır. İşlerin sistemde geçirdikleri bekleme süresinin artması işlem sürelerini uzatırken kalitelerini ise zamanla bozmaktadır. İşlem süresi ve kalite fonksiyonlarının doğrusal formlar aldığı çizelgeleme problemini analiz ediyoruz ve çözmeye çalışıyoruz. Problem önce karışık tamsayılı bir lineer program olarak formüle ediliyor ve sınırlı problem boyutları için en iyi çözümler elde ediliyor. Daha sonra sorunu çözmek için sezgisel bir algoritma ve bekleyen işleri sıralamak için yeni fikirler geliştiriyoruz. Doğrusal ve poisson regresyon modelleri, işlerin makinelerdeki öncelik sırasını tahmin etmek için geliştirildi ve ayrıca daha iyi sıralama yaklaşımları sağlamak için sıra kümelemesi yöntemi kullanıldı.