A branch and bound approach for single machine scheduling problem

Yükleniyor...
Küçük Resim

Tarih

2017

Dergi Başlığı

Dergi ISSN

Cilt Başlığı

Yayıncı

İstanbul Ticaret Üniversitesi

Erişim Hakkı

info:eu-repo/semantics/openAccess

Özet

Last decades, scheduling problems have attracted researchers because of the fact that they play a critical role in production planning. This paper studies to minimize the sum weight of lateness on a single machine scheduling problem. There are given n jobs and for each job we have a release date, a processing time, a due date and weight in a constraint working environment. Single machine models are important for various reasons because of the fact that it not only provides insights into the single machine environment but also bottleneck problem. There are various exact methods in order to solve single machine scheduling problem with make span objective function. However, if the objective functions is tardiness, lateness, weighted tardiness, weighted lateness etc. to find exact solution is very difficult. In this paper, branch and bound method is proposed to solve single machine scheduling problem with the total weighed lateness objective for small number of job. The proposed method has applied on a job size of 4, 5 and 8 and provides optimal result.
Son yıllarda çizelgeleme problemleri üretim planlamada kritik bir rol oynadığı için araştırmacıların ilgisini çekmektedir. Bu çalışmada toplam ağırlıklı gecikme süresi minimizasyonu amaçlı tek makine çizelgeleme problemi ele alınmıştır. Verilen n iş için işlerin geliş süresi, müşteriye teslim süresi, işlem süreleri ve iş çevresinin kısıtlarından kaynaklanan işlerin ağırlıkları verilmiştir. Tek makine modelleri sadece tek makine ortamı için bir bakış açısı kazandırmasından değil aynı zamanda darboğaz problemlerinin çözümü için de bir bakış sağladığı için önemlidir. Toplam tamamlanma süresi minimizasyonu için tek makine çizelgeleme problemlerini çözmek için tam çözüm veren birçok metot vardır. Bununla birlikte, gecikme, erken bitirme, ağırlıklı gecikme amaçları söz konusu olduğunda tam çözüm bulmak çok zordur. Bu çalışmada az sayıda iş içeren, toplam ağırlıklı gecikme minimizasyonu problem için dal-sınır algoritması önerilmiştir. Önerilen model 4, 5 ve 8 adet iş için gerçek hayat verileri kullanılarak uygulanmış ve en uygun sonuç alınmıştır.

Açıklama

Anahtar Kelimeler

Scheduling, Single Machine Scheduling, Weighted Total Lateness Minimization, Branch & Bound, Çizelgeleme, Tek Makine, Toplam Ağırlıklı Gecikme Minimizasyonu, Dal & Sınır

Kaynak

İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi

WoS Q Değeri

Scopus Q Değeri

Cilt

16

Sayı

31

Künye