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

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

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.

Keywords:

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

PDF

___

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.