A branch and bound approach for single machine scheduling problem
Yükleniyor...
Dosyalar
Tarih
2017
Yazarlar
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.
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