Duygu EROĞLU YILMAZ, H. Cenk ÖZMUTLU, Seyit Ali KÖKSAL

A genetic algorithm for the unrelated parallel machine scheduling problem with job splitting and sequence-dependent setup times - loom scheduling

Bu çalışmada, bölünebilir ve sıra bağımlı hazırlık süreli işler içeren, ilişkisiz paralel makine çizelgeleme probleminde, en büyük tamamlanma zamanının en küçüklenmesi hedeflenmiştir. Çalışmada, tekstil endüstrisinde, dokuma tezgâhlarının çizelgelenmesi gerçek problemi dikkate alınmıştır. Her makineye özgü, işi tipine ve makine yapısına bağlı olarak değişen işleme süreleri söz konusudur. Makine ve iş sırası bağımlı hazırlık süreleri de mevcuttur ve tüm işler sıfır anında hazırdır. Tüm işler, zamanında teslimatı sağlayabilmek için, alt işlere bölünebilmektedir. İşlerin bölünmesi durumu, özellikle de paralel makinelerde, literatürde nadiren çalışılmıştır. Problemin NP-zor yapısından dolayı, gerçek hayata dair, büyük boyutlu problemlerin çözümü için sezgisel ve meta- sezgisel yöntemler kullanılmaktadır. Genetik algoritmalar (GA), yüksek adaptasyon ve kolay gerçekleşme özelliklerinden dolayı en çok tercih edilen yaklaşımlardır. Önerilen genetik algoritmanın kromozom temsili, rassal anahtar sayılara dayanmaktadır. Çizelge, rassal anahtar sayıların sıralanması ile oluşturulmaktadır. Bu makalenin literatüre ana katkısı, iş bölme ve çizelgelemeyi eş zamanlı yapabilen yeni bir yaklaşım önermesidir. Bilindiği kadarıyla literatürde bu yaklaşımda bir çalışma mevcut değildir. Makalede önerilen diğer önemli geliştirme ise alt iş sayılarının dinamik olarak atanmasıdır. İlave olarak, yeni yaklaşım gerçek hayat probleminde test edilmiş ve hesaplama sonuçları, önerilen algoritmanın etkinliğini doğrulamıştır.

Bölünebilir ve sıra bağımlı hazırlık süreli işler içeren, ilişkisiz paralel makine çizelgeleme problemi için genetik algoritma-dokuma tezgâhı çizelgeleme

This paper addresses the unrelated parallel machine scheduling problem with sequence-dependent setup times and job splitting to minimize maximum completion time (makespan). We consider a real-life problem of scheduling looms in a textile industry. Each machine has its own processing times according to the characteristics of the machine as well as the job types. There are machine- and sequence-dependent setup times, and all of the jobs are available at time zero. All of the jobs can be divided into sub-jobs in order to deliver the orders on time. Job splitting has rarely been studied in the literature, especially in the case of parallel machines. Because of the problem s NP-hard structure, heuristics and metaheuristics have been used to solve real-life large-scale problems. Genetic algorithms (GA) are the most preferred approach of this type given their capabilities, such as high adaptability and easy realization. The proposed GA s chromosome representation is based on random keys. The schedule is constructed using a sequence of random key numbers. The main contribution of this paper is to introduce a novel approach that performs job splitting and scheduling simultaneously; to the best of our knowledge, no work has been published with this approach. An important improvement proposed in this paper is assigning the number of sub-jobs dynamically. In addition, the new approach is tested on a real-life problem, and the computational results validate the effectiveness of the proposed algorithm.

PDF

___

1.Vallada, E., & Ruiz, R. (2011). A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times, European Journal of Operational Research, 211, 612622.
2.Kashan, A.H., Karimi, B., & Jolai,F. (2010). An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single batch processing machine with non-identical job sizes, Engineering Applications of Artificial Intelligence, 23, 911922.
3.Yalaoui, F., & Chu, C. (2003). An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times, IIE Transactions, 35(2), 183190.
4.Eroglu, D.Y., Ozmutlu H.C., & Ozmutlu S. (2013). Genetic algorithm with local search for the unrelated parallel machine scheduling problem with sequence-dependent setup times, International Journal of Production Research, Manuscript submitted for publication.
5.SchedulingResearch. (2005). Accessed June 07, 2012 from http://SchedulingResearch.com
6.Allahverdi, A., Ng, C.T., Cheng, T.C.E., & Kovalyov, M.Y. (2008). A survey of scheduling problems with setup times or costs, European Journal of Operational Research, 187, 9851032.
7.Zhu, X., Wilhelm, & W.E. (2006). Scheduling and lot sizing with sequence-dependent setup: A literature review, IIE Transactions, (38), 9871007.
8.Li, K., & Yang, S. (2009). Non-identical parallel-machine scheduling research with minimizing total weighted completion times: Models, relaxations and algorithms, Applied Mathematical Modelling, 33, 21452158.
9.Lin, Y.K., Pfund, M.E., & Fowler, J.W. (2011). Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems, Computers & Operations Research, 38, 901916.
10. Park, Y., Kim, S., & Lee, Y.H. (2000). Scheduling jobs on parallel machines applying neural network and heuristic rules, Computers & Industrial Engineering, 38, 189-202.
11. Lee, Y. H., Bhaskaran, K., & Pinedo, M. (1997). A heuristic to minimize the total weighted tardiness with sequence-dependent setups, IIE Transactions, 29, 45-52.
12. Hop, N.V., & Nagarur, N.N. (2004). The scheduling problem of PCBs for multiple non-identical parallel machines, European Journal of Operational Research, 158, 577594.
13. Behnamian, J., Zandieh, M., & Ghomi, S.M.T.F. (2009). Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm, Expert Systems with Applications, 36, 96379644.
14. Yang, T. (2009). An evolutionary simulationoptimization approach in solving parallel-machine scheduling problems A case study, Computers & Industrial Engineering, 56, 11261136.
15. Balin, S. (2011). Non-identical parallel machine scheduling using genetic algorithm, Expert Systems with Applications, 38, 68146821.
16. Keskinturk, T., Yildirim, M.B., & Barut, M. (2012). An ant colony optimization algorithm for load balancing in parallel machines with sequence-dependent setup times, Computers and Operations Research, 39, 12251235.
17. Rabadi, G., Moraga, R., & Al-Salem, A. (2006). Heuristics for the Unrelated Parallel Machine Scheduling Problem with Setup Times, Journal of Intelligent Manufacturing, 17, 8597.
18. Arnaout, J.P., Rabadi, G., & Musa, R. (2010). A two-stage Ant Colony Optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times, Journal of Intelligent Manufacturing, 21, 693-701.
19. Chang, P.C., & Chen, S.H. (2011). Integrating dominance properties with genetic algorithms for parallel machine scheduling problems with setup times, Applied Soft Computing, 11, 12631274.
20. Kim, D.W., Kim, K.H., Jang, W., & Chen, F.F. (2002). Unrelated parallel machine scheduling with setup times using simulated annealing, Robotics and Computer Integrated Manufacturing, 18, 223231.
21. Kim, Y.D., Shim, S.O., Kim, S.B., Choi, Y.C., & Yoon, H.M. (2004). Parallel machine scheduling considering a job-splitting property, International Journal of Production Research, 42, 453146.
22. Shim, S.O., & Kim, Y.D. (2008). A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property, Computers & Operations Research, 35, 863 875.
23. Xing, W., & Zhang, J. (2000). Parallel machine scheduling with splitting jobs, Discrete Applied Mathematics, 103, 259-269.
24. Tahar, D.N., Yalaoui, F., Chu, C., & Amodeo, L. (2006). A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times, International Journal of Production Economics, 99, 6373.
25. Serafini, P. (1996). Scheduling jobs on several machines with the job splitting property, Operations Research, 44, 617628.
26. Holland, J.A. (1975). Adaptation in natural and artificial systems: University of Michigan, Ann Arbor.
27. Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning: Addison-Wesley, Reading.
28. Haupt, R. L., & Haupt S. E. (2004). Practical Genetic Algorithms, New Jersey: Second edition, John Wiley & Sons Inc.
29. Minitab 16, Statistical Software (2010). State College, PA: Minitab, Inc. (www.minitab.com).