Unrelated parallel machines scheduling under machine availability and eligibility constraints

Abstract

Paralel makinelerin çizelgelenmesi literatüründe genellikle makinelerin her zaman işlem görmeye hazır olduğu ve her işin herhangi bir makinede işlem görebileceği varsayılır. Oysa ki, bazı imalat ortamlarında bu varsayımlar gerçek dışı kalmaktadır. Bu çalışmada, makine kullanılırlık ve elverişlilik kısıtları altında n tane işin m tane özdeş olmayan paralel makinelerde iş çizelgelemesi problemi, her bir makinenin bakım işleri öncesinde kesintisiz bir şekilde en çok çalışabileceği süre ve bakım işleri süresi bilindiği durum için ele alınmıştır. Amacımız, maksimum tamamlanma zamanını (tüm işlerin bitirilme süresini) enazlamaktır. İşlerin devam ettirilebilir ve ettirilemez olabildiği durumların her ikisi de ele alınmış ve her iki problemin optimum çözümü için karışık tamsayılı bir doğrusal programlama modeli ile sezgisel çözüm algoritmaları geliştirilmiştir. Ayrıca, bu yöntemlerin çözüm üretme performansları hem çözüm kalitesi hem de zaman yönünden sınanmıştır. Sonuçlar, önerilen sezgisel yöntemlerin çok kısa sürede optimal çözüme yakın çözümler bulduğunu göstermiştir.

In the literature of the parallel machines scheduling, it is generally assumed that all machines are continuously available for processing jobs and each job can be processed by any machine. However, these assumptions become unrealistic in some industrial environments. In this study, we consider the problem of scheduling n independent jobs on m unrelated parallel machines subject to machine availability and eligibility constraints, given the maximum continuous working time before the maintenance of each machine and the maintenance time. Our objective is to minimize the makespan, which is the time to complete the processing of all jobs. We consider both resumable and non-resumable jobs, and develop mathematical models and heuristic algorithm that obtain exact and near-optimal solutions, respectively, for both cases with multiple machine unavailability periods. Computational experiments are done to evaluate the performance of our solution methods in terms of both quality and time. The results show that the proposed heuristic algorithm finds near-optimal solutions in very short time.