HIZ DEĞİŞTİRME FAALİYETLİ TEK MAKİNELİ ÇİZELGELEME PROBLEMİ İÇİN EN KISA YOL TABANLI BİR ÇÖZÜM YÖNTEMİ

Yıl 2019, Cilt: 8 Sayı: 2, 842 - 849, 31.07.2019

Gül Didem Batur Sir

https://doi.org/10.28948/ngumuh.536457

Cited By: 1

Öz

   Bu çalışmada, tek makineli bir sistemde hız
değiştirme faaliyeti (HDF) ile birlikte işlerin çizelgelenmesi üzerinde
durulmaktadır. Bir HDF, makinenin üretim hızının orijinal durumuna getirilmesi
için uygulanan bir bakım faaliyeti olarak tanımlanmaktadır. Bu açıdan
bakıldığında, bir işin HDF’den önce veya sonra planlanması sonucunda, işlerin
işlem zamanları farklı değerler almaktadır. Ele alınan problem, iş sırası ve bu
iş sırası içindeki HDF konumunun belirlenmesidir. Çözüme yönelik olarak şebeke
gösterimine dayalı, en kısa yol tabanlı bir yöntem oluşturulmuştur. Önerilen yöntemde,
ilk aşamada En Kısa İşlem Zamanı algoritması ile elde edilmiş iş sıralamasına
göre bir şebeke oluşturulmaktadır. Daha sonra ilgili şebeke üzerinde en kısa
yolu veren HDF ataması doğrusal programlama kullanılarak aranmakta ve bulunan
yolun değeri makine için toplam tamamlanma zamanını vermektedir. Bundan sonra
yerel arama prosedürü uygulanarak, her adımda iş sıralamaları üzerinde swap operasyonu (ikili değişim)
kullanılmakta ve elde edilen yeni çözümler üzerinde yapılan sürekli
karşılaştırmalar sonucu son çözüm elde edilmektedir.

Anahtar Kelimeler

Makine çizelgeleme, hız değiştirme faaliyeti, en kısa yol algoritması, tam sayılı programlama

A SHORTEST PATH BASED SOLUTION METHOD FOR SINGLE MACHINE SCHEDULING PROBLEM WITH RATE MODIFYING ACTIVITY

Öz

   In this study, scheduling of jobs and a rate
modifying activity (RMA) on a single machine system is considered. A RMA is
defined as a maintenance activity applied to bring production speed of the
machine back to its original state. From this point of view, when a job is
planned before or after the RMA, processing times of the jobs become different.
The problem addressed is determination of the job sequence and the position of
the RMA in this sequence. A shortest path-based method which is based on
network representation is developed for the solution. In the proposed method, a
network is created in the first step according to the job sequence obtained by
the Shortest Processing Time algorithm. RMA assignment that gives the shortest
path on the network is then searched using linear programming and the value of
the found path gives total completion time for the machine. After this, using
local search procedure, swap
operation (binary exchange) is applied on the job positions at each step and
final solution is obtained as a result of continuous comparisons on new
solutions obtained.

Anahtar Kelimeler

Machine scheduling, rate modifying activity, shortest path algorithm, integer programming

Kaynakça

• LEE C.Y., LEON V.J., “Machine Scheduling with a Rate Modifying Activity”, European Journal of Operations Research, 128, 119-128, 2001.
• WHITAKER, L.O., Integrated Production and Maintenance Activities, M.S. Thesis, Department of Industrial Engineering, Texas A&M University, College Station, TX, 1996.
• LEE, C.Y., LIN, C.S., “Single Machine Scheduling with Maintenance and Repair Rate-Modifying Activities”, European Journal of Operational Research, 135, 495-513, 2001.
• MOSHEIOV, G., SIDNEY, J., “New Results on Sequencing with Rate Modification”, Information Systems and Operational Research, 41(2), 155–163, 2003.
• MOSHEIOV G., ORON D., “Due-Date Assignment and Maintenance Activity Scheduling Problem”, Mathematics & Computer Modelling, 44, 1053-1057, 2006.
• GORDON V.S., TARASEVİCH A.A., “A Note: Common Due Date Assignment for a Single Machine Scheduling with the Rate-Modifying Activity”, Computers & Operational Research, 36, 325-328, 2009.
• WANG X.Y., WANG M.Z., “Single Machine Common Flow Allowance Scheduling with a Rate-Modifying Activity”, Computers & Industrial Engineering, 59(4), 898-902, 2010.
• MOSHEIOV G., SIDNEY J.B., “Scheduling a Deteriorating Maintenance Activity on a Single Machine”, Journal of the Operational Research Society, 61, 882-887, 2010.
• ZHAO C., TANG H., “A note to due-window assignment and single machine scheduling with deteriorating jobs and a rate-modifying activity”, Computers & Operations Research, 39(6): 1300-1303, 2010.
• ZHU Z., CHU F., SUN L., LIU M., “Single machine scheduling with resource allocation and learning effect considering the rate-modifying activity”, Applied Mathematical Modelling, 37: 5371-5380, 2013.
• PINEDO, M.L., Scheduling: Theory, Algorithms and Systems, Prentice-Hall, Englewood Cliffs, NJ, 1995.
• BATUR SİR, G.D., “Hız değiştirme faaliyeti ile tek makineli çizelgeleme problemi için şebeke tabanlı bir matematiksel model”, Proceedings of the International Conference on Mathematics – Engineering – Natural & Medical Sciences, Adana, Türkiye, 2019.
• MILLER C., TUCKER A., ZEMLIN R., “Integer Programming Formulation of Traveling Salesman Problems”, Journal of the ACM, 7(4), 326-329, 1960.