Paralel Makina Çizelgeleme Problemi için bir Karma Tamsayılı Programlama Modeli: Ortak Kaynak Kullanımı

Year 2017, Volume: 5 Issue: 3, 109 - 126, 15.09.2017

Emine Akyol Tuğba Saraç

Abstract

Paralel makina çizelgeleme problemlerinde, bazı işler ortak kaynak kullanıyorlarsa bu işleri aynı anda çizelgelemek mümkün değildir. Örneğin, eğer iki plastik parça aynı kalıp ile üretiliyorsa biri üretilirken diğeri kalıbı beklemek zorundadır. Paralel makinaların olduğu pek çok üretim sisteminde, işler kalıp, kreyn v.b. ortak kaynaklar kullanmaktadırlar. Bu çalışmada, ortak kaynak kullanan işlerin paralel makinalarda çizelgelenmesi problemi ele alınmıştır. Ele alınan problem için bir karma tamsayılı programlama modeli geliştirilmiştir. Önerilen modelin GAMS/Cplex ile çözüm performansı, rassal olarak türetilmiş küçük ve büyük boyutlu test problemleri kullanılarak test edilmiştir.

Keywords

Paralel makine çizelgeleme, Sıra bağımlı hazırlık süresi, Makine uygunluk kısıtları, Ortak kaynak kullanımı, Karma tamsayılı programlama

A Mix Integer Programming Model for Parallel Machine Scheduling Problem: Using Shared Resource

Abstract

In parallel machine scheduling problems, if jobs have shared resources, it is not possible to schedule these jobs at the same time. For instance, if same mold are used for producing two different plastic parts, one of the parts has to wait until the end of other part’s process. In production systems including parallel machines, in general, jobs use shared resources like mold, crane etc. In this study, an identical parallel machine scheduling problem with shared resources is considered. A mixed-integer programming model is developed for considered problem. The solving performance of proposed model by GAMS/Cplex solver was tested using randomly generated small and large-sized instances

Keywords

Parallel machine scheduling problem, Sequence dependent setup time, Machine eligibility restrictions, Using shared resources, Mixed integer programming

References

• [1] New York University Stern School of Business. Introduction. http://www.stern.nyu.edu/om/faculty/pinedo/scheduling/shakhlevich/handout01.pdf. Yayın tarihi Ocak 30, 2017. Erişim tarihi Mart 3, 2017.
• [2] T. Saraç, Genelleştirilmiş Karesel Çoklu Sırt Çantası Problemi İçin Melez Bir Çözüm Yaklaşımı, Doktora Tezi, Osmangazi Üniversitesi Fen Bilimleri Enstitüsü, 2007.
• [3] J. P. Arnaout, Heuristics for the Maximization of Operating Rooms Utilization Using Simulation. Simulation, 86:8-9 (2010) 573-583.
• [4] J. R. M. Torres, M. S. Ferrari, F. G. Solano, Production Scheduling with Sequence Dependent Setups and Job Release Times. Dyna-Colombia, 77:163 (2010) 260-269.
• [5] B. K. Kim, Y. D. Kim, Heuristic algorithms for assigning and scheduling flight missions in a military aviation unit. Computers & Industrial Engineering, 61:4 (2011) 1309-1317. Doi: 10.1016/j.cie.2011.08.004.
• [6] S. H. Chung, Y.T. Tai, W.L. Pearn, An Effective Scheduling Approach for Maximizing Polyimide Printing Weighted Throughput in Cell Assembly Factories. IEEE Transactions on Electronics Packaging Manufacturing, 32:3 (2009) 185-197.
• [7] R. Driessel, L. Moench, Scheduling Jobs on Parallel Machines with Sequence Dependent Setup Times Precedence Constraints and Ready Times Using Variable Neighborhood Search. International Conference on Computers and Industrial Engineering, Troyes, FRANCE, 06-09 July 2009.
• [8] X. Li, Y.Farouk, A. Lionel, A Multi Objective Meta-heuristic with A Fuzzy Logic Controller for Solving A Scheduling Problem. Computational Intelligence: Foundations and Applications: Proceedings of the 9th International FLINS Conference, Emei, CHINA, 02-04 August 2010.
• [9] S. W. Lin, Z. J. Lee, K. C. Ying, C. C. Lu, Minimization of maximum lateness on parallel machines with sequence-dependent setup times and job release dates. Computers & Operations Research, 38:5 (2011) 809-815.
• [10] A. K. Türker, Ç. Sel, Scheduling two parallel machines with sequence-dependent setups and a single server. Gazi University Journal of Science, 24:1 (2011) 113-123.
• [11] A. K. Türker, C. Sel, A Hybrit Approach on Single Server Parallel Machines Scheduling Problem with Sequence Dependent Setup Times. Journal of the Faculty of Engineering and Architecture of Gazi University, 26:4 (2011) 731-740.
• [12] O. Alagoz, M. Azizoglu, Rescheduling of identical parallel machines under machine eligibility constraints. European Journal of Operational Research, 149:3 (2003) 523-532.
• [13] D. T. Eliiyi, M. Azizoglu, A fixed job scheduling problem with machine-dependent job weights. International Journal of Production Research, 47:9 (2009) 2231-2256.
• [14] L. H. Su, W. Y. Chang, F. D. Chou, Minimizing maximum lateness on identical parallel machines with flexible resources and machine eligibility constraints. International Journal of Advanced Manufacturing Technology, 56:9-12 (2011) 1195-1204.
• [15] K. Li, Ye Shia, Shan-lin Yanga, Ba-yi Cheng, Parallel machine scheduling problem to minimize the makespan with resource dependent processing times, Applied Soft Computing, 11:8 (2011) 5551-5557.
• [16] E. B. Edis, C. Oguz, I. Ozkarahan, Solution Approaches for Simultaneous Scheduling of Jobs and Operators on Parallel Machines. Journal of the Faculty of Engineering and Architecture of Gazi University, 27:3 (2012) 527-535.
• [17] R. Ruiz, C. A. Romano, Scheduling unrelated parallel machines with resource-assignable sequence-dependent setup times. International Journal of Advanced Manufacturing Technology, 57:5-8, (2011) 777-794.
• [18] E. B. Edis, I. Ozkarahan, A Combined Integer/Constraint Programming Approach to a Resource Constrained Parallel Machine Scheduling Problem with Machine Eligibility Restrictions. Engineering Optimization, 43:2 (2011) 135-157.
• [19] E. B. Edis, C. Oguz, Parallel machine scheduling with flexible resources. Computers & Industrial Engineering, 63:2 (2012) 433-447.
• [20] O. Avalos-Rosales, F. Angel-Bello, A. Alvarez, Efficient metaheuristic algorithm and re-formulations for the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times. International Journal of Advanced Manufacturing Technology, 76:9-12 (2015) 1705-1718.
• [21] B. Gacias, C. Artigues, P. Lopez, Parallel machine scheduling with precedence constraints and setup times. Computers & Operations Research, 37:12 (2010) 2141-2151.
• [22] C. L. Chen, C. L. Chen, Hybrid meta-heuristics for unrelated parallel machine scheduling with sequence-dependent setup times. International Journal of Advanced Manufacturing Technology, 43: 1-2 (2009) 161-169.
• [23] R. Nessah, C. Chengbin, F. Yalaoui, An exact method for 𝑃𝑚/𝑠𝑑𝑠/Σ𝑐𝑖𝑛𝑖=1 problem. Computers & Operations Research, 34:9 (2007) 2840-2848.