A BRANCH AND BOUND APPROACH FOR SINGLE MACHINE SCHEDULING PROBLEM

Year 2017, Volume: 16 Issue: 31, 43 - 55, 30.06.2017

Sebrina Tadesse Dawd Berk Ayvaz

Abstract

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.

Keywords

Scheduling, Single Machine, Weighted Total Lateness Minimization, Branch & Bound

TEK MAKİNE ÇİZELGELEME PROBLEMİ İÇİN DAL SINIR YAKLAŞIMI

Abstract

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.

Keywords

Çizelgeleme, tek makine, toplam ağırlıklı gecikme minimizasyonu, dal & sınır

References

• Atan M. O., Akturk M. S., (2008), Single CNC machine scheduling with controllable processing times and multiple due dates, International Journal of Production Research 46, 6087-6111.
• Baker K. R. and Trietsch D., (2009), Principles of sequencing and scheduling, A John Wiley& Sons Inc, Hoboken, New Jersey, 2009. Batsyn M., Goldengorin B., Pardalos M. Sukhov P., (2014), Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time, Journal of Optimization Methods and Software, 23(5), 13-17.
• Batun S. and Azizoğlu M., (2009), Single machine scheduling with preventive maintenance, International Journal of Production Research, Vol. 47, No. 7, 1753–1771.
• Benmansour R., Hamid A.& Artiba A., (2012), Stochastic single machine scheduling with random common due date, Journal International Journal of Production Research, Volume 50, 2012 -Issue 13.
• Bülbül K., Kaminsky P., and Yano C., (2007), Preemption in single machine earliness/tardiness scheduling, Springer Science and Business Media, LLC 2007.
• Chang P.C, Chung Y.K., Hsieh, J.C., (2004), On single-machine scheduling with release times to minimize total weighted completion time, Journal of the Chinese Institute of Industrial Engineers, Vol. 21, 567-575.
• Du J., Leung J.Y.T., (1990), Minimizing total tardiness on one machine is NP-hard; Mathematics of Operations Research Vol. 15, No. 3 (Aug., 1990), 483-495.
• Gordon, V., Potapneva E. and Werner F., (1997), Single machine scheduling with deadlines, release and due dates, Optimization, 42, 219-244.
• Gupta J.N.D., & Chantaravarapan S., (2008), Single machine group scheduling with family setups to minimize total tardiness, International Journal of Production Research 46, 1707–1722.
• Hoogeveen J.A., (2005), Multicriteria scheduling, European Journal of Operational Research Volume 167, Issue 3, 16 December 2005, 592-623.
• Lawler E.L., (2005), A “Pseudopolynomial” Algorithm for Sequencing Jobs to Minimize Total Tardiness, Annals of Discrete Mathematics Volume 1, 1977, 331-342.
• Lee W., Shiau Y., Chung Y., and Lawson D., (2014), Single-Machine Scheduling to Minimize Total Completion Time and Tardiness with Two Competing Agents, the Scientific World Journal Volume 2014.
• Lenstra J.K., Rinnooy A.H.G.K., and Brucker P., (1977), Complexity of machine scheduling problems, Annals of Discrete Mathematics, Vol. 1(1977), 343-362.
• Tanaka S., (2012), An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem, Just-in-Time Systems, Volume 60 of the series, Springer Optimization and Its Applications, 21-40.
• Yang D.L., Hung C.L., Hsu C.J., Chern M.S., (2002), Minimizing the makespan in a single machine scheduling problem with a flexible maintenance, Journal of the Chinese Institute of Industrial Engineers, 19, 63-66.
• Yurtkuran A. & Emel E., (2016), A discrete artificial bee colony algorithm for single machine scheduling problems, International Journal of Production Research, 54:22, 6860-6878.
• Zhang L., Guan L., Zhou K., (2014), Stochastic Machine Scheduling to Minimize Waiting Time Related Objectives with Emergency Jobs; Discrete Dynamics in Nature and Society, Volume 2014.