Operational fixed job scheduling problem

---

Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2004

Öğrenci: DENİZ TÜRSEL ELİİYİ

Danışman: MERAL AZİZOĞLU

Özet:

In this study, we consider the Operational Fixed Job Scheduling Problem on identical parallel machines. The problem is to select a subset of jobs for processing among a set of available jobs with fixed arrival times and deadlines, so as to maximize the total weight. We analyze the problem under three environments: Working time constraints, Spread time constraints, and Machine dependent job weights. We show that machine eligibility constraints appear as a special case of the last environment. We settle the complexity status of all problems, and show that they are NP-hard in the strong sense and have several polynomially solvable special structures. For all problems, we propose branch and bound algorithms that employ powerful reduction mechanisms and efficient lower and upper bounds. The results of our computational runs reveal that, the algorithms return optimal solutions for problem instances with up to 100 jobs in reasonable solution times.