Bozulma ve öğrenme etkileri altında çok ajanlı çizelgeleme problemleri için çözüm yaklaşımları
Solution approaches for multi-agent scheduling problems under deterioration and learning effects
Yazar: TUĞBA DANACI
Danışman: PROF. DR. MEHMET DURAN TOKSARI
Erciyes Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2022
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering
Dizin: Bozulma = Degradation ; Dal sınır algoritması = Branch bound algorithm ; Çizelgeleme = Scheduling ; Öğrenme etkisi = Learning effect

Özet:
Günümüzde çizelgeleme problemleri çok ajanlı ve değişken işlem süreli işlerin çizelgelenmesine odaklanmaktadır; fakat çok ajanlı hem öğrenme hem de bozulma etkisi altında çizelgeleme problemleri çok fazla çalışılmamıştır. Birden fazla amacın söz konusu olduğu ve aynı kaynakları kullanmaları gereken işlerin çizelgelenme problemleri "Çok Ajanlı Çizelgeleme Problemleri (MASP)" olarak tanımlanmaktadır. Bu çalışmada rekabet halinde olan iki ajana ait ve proses süreleri simultane şekilde öğrenme ve bozulma etkileri ile değişen işlerin tek makine ortamında çizelgelenmesi problemi ele alınmıştır. Ajanlara ait işlerin işlem süreleri sabit olmayıp; öğrenme etkisi altında olmalarından dolayı çizelgedeki pozisyonlarına bağlı olarak azalmakta; aynı zamanda bozulma etkisi altında olmalarından dolayı işlerin başlangıç zamanına bağlı olarak artmaktadır.  Çalışma kapsamında ikinci ajana ait hiçbir işin gecikmesine izin verilmemesi kısıtı altında, birinci ajan için toplam ağırlıklı tamamlama süresinin en aza indirgenmesi amaçlanmıştır. Problem için iki aşamalı bir metodoloji geliştirilmiştir. İlk aşamada, başlangıç çözümü için sezgisel bir yöntem önerilmiş; ikinci aşamada baskınlık kurallarının da oluşturulduğu dal-sınır algoritması ile optimal sonuç elde edilmeye çalışılmıştır. Geliştirilen yöntem ile 25 işe kadar olan problemlerde uygun çözümler elde edildiği; öğrenme etkisinin daha düşük olduğu ve bozulma etkisinin daha yüksek olduğu problemlerde bu sayının artabileceği gösterilmiştir.

Anahtar Kelimeler: Çok ajanlı çizelgeleme, Değişken işlem süresi, Öğrenme etkisi, Bozulma etkisi, Dal-sınır algoritması

Abstract:
Recent scheduling studies focus on variable job-processing-times and multi-agent problems simulataneously; but a few of them studied multi agent scheduling problems under the simulataneous effect of learning and deterioration. The scheduling problems that have more than one purpose and need to use the same resources are defined as "Multi-Agent Scheduling Problems (MASP)". This thesis studies a two-competing-agent single-machine scheduling problem with jobs under simulataneous learning and deterioration effect. Because jobs are under the learning effect, their processing time decreases as their position in the schedule increases; however, since the work is under the effect of deterioration, it increases depending on the execution start time. The goal of this study is to find an optimal solution to minimize total weighted completion time for the first agent subject to the restriction that no tardy job is allowed for the second agent. A two-stage methodology has been developed for the problem. In the first stage, a heuristics is proposed to find the near-optimal solution of which is used as input for the second stage. For second stage, a branch-and-bound algorithm along with several dominances and a lower bound is developed to find the optimal solution. Computational experiments are provided to further measure the performance of the proposed algorithms.

Keywords: Multi-agent scheduling, Variable processing times, Learning effect, Deterioration effect, Branch-and-bound algorithm