Solution Representation in Proportionate Multiprocessor Open Shop

Öz

Proportionate multiprocessor open shop is considered in this study. It is a shop model where a set of jobs follow no predefined route to visit several stages with at least one having two or more parallel machines to carry out the same task. Proportionality means that processing times depend only on stages and are independent of jobs, hence is defined as stage-wise. The shop model has various application areas in industry but the literature on the field is still limited. In this study, a novel solution representation scheme is proposed for the proportionate multiprocessor open shop. The scheme is based on permutation of stages and encodes the cumulative number of job assignments to a stage. The proposed scheme is shown to generate higher quality random solutions compared to the common operation permutation representation for the shop model. The approach proposed in this study to design a solution representation for a scheduling problem is a new and favorable approach that takes into account the specific machine environment, job characteristics and objective function of the problem under consideration. This way of designing solution representation schemes would increase the solution quality or decrease the computational time required in solution algorithms for scheduling problems.

Anahtar Kelimeler

• Multiprocessor open shop
• solution representation
• implicit-stage representation
• scheduling
• proportionate

Orantılı Esnek Açık Atölye Tipinde Çözüm Gösterimi

Öz

Bu çalışmada orantılı esnek açık atölye tipi ele alınmıştır. Bu atölye modelinde yapılacak işlerin işlem istasyonlarını gezerken takip edecekleri bir rota bulunmaz ve bu istasyonların en az birinde aynı işlemi yapan iki veya daha fazla paralel makine bulunur. Orantılı ifadesi işlem sürelerinin istasyona bağlı olduğunu ve işten bağımsız olduğunu ifade eder. Böylece, orantılılık istasyon-bazlı olarak tanımlanmıştır. Bu atölye modelinin endüstride farklı uygulama alanları mevcuttur ancak bu alandaki literatür hala kısıtlıdır. Bu çalışmada, orantılı esnek açık atölye tipi için yeni bir çözüm gösterimi önerilmiştir. Önerilen gösterim istasyonların permutasyonuna dayanır ve bir istasyona yapılan kümülatif iş ataması sayısını şifreler. Önerilen bu yeni gösterim, bu atölye tipinde yaygın olarak kullanılan operasyon-permütasyonu gösteriminden daha iyi kalitede rastgele çözümler üretmiştir. Bu çalışmada çizelgeleme probleminde çözüm gösterimi tasarımında kullanılan yaklaşım yeni ve sonuçlar bakımından olumludur. Bu yaklaşım eldeki probleme özel makine ortamını, iş özelliklerini ve amaç fonksiyonunu dikkate alır. Çözüm gösterimi tasarlanmasında izlenen bu yol çizelgeleme problemlerinde kullanılan çözüm algoritmalarının daha yüksek kalitede çözüme ulaşmasını veya harcanan hesaplama zamanının kısaltılmasını sağlayacaktır.

Anahtar Kelimeler

• Esnek açık atölye
• çözüm gösterimi
• istasyon gösterimi
• çizelgeleme
• orantılı

Kaynakça

1. Abdelmaguid, T. F. 2020. Scatter search with path relinking for multiprocessor open shop scheduling. Computers & Industrial Engineering, 141, 106292.
2. Abdelmaguid, T. F., Shalaby, M. A. & Awwad, M. A. 2014. A tabu search approach for proportionate multiprocessor open shop scheduling. Computational Optimization and Applications, 58, 187-203.
3. Adak, Z. 2020. An ant colony optimization approach for the proportionate multiprocessor open shop. PhD Doctoral thesis, Marmara University.
4. Adak, Z., Arıoğlu Akan, M. Ö. & Bulkan, S. 2020. Multiprocessor open shop problem: literature review and future directions. Journal of Combinatorial Optimization, 40, 547-569.
5. Azadeh, A., Hosseinabadi Farahani, M., Torabzadeh, S. & Baghersad, M. 2014. Scheduling prioritized patients in emergency department laboratories. Computer Methods and Programs in Biomedicine, 117, 61-70.
6. Bai, D., Zhang, Z.-H. & Zhang, Q. 2016. Flexible open shop scheduling problem to minimize makespan. Computers & Operations Research, 67, 207-215.
7. Chen, B., Potts, C. N. & Woeginger, G. J. 1998. A Review of Machine Scheduling: Complexity, Algorithms and Approximability. In: DU, D.-Z. & PARDALOS, P. M. (eds.) Handbook of Combinatorial Optimization: Volume1–3. Boston, MA: Springer US.
8. Goldansaz, S. M., Jolai, F. & Zahedi Anaraki, A. H. 2013. A hybrid imperialist competitive algorithm for minimizing makespan in a multi-processor open shop. Applied Mathematical Modelling, 37, 9603-9616.

9. Gonzalez, T. & Sahni, S. 1976. Open Shop Scheduling to Minimize Finish Time. J. ACM, 23, 665–679.
10. Liaw, C.-F. 2000. A hybrid genetic algorithm for the open shop scheduling problem. European Journal of Operational Research, 124, 28-42.
11. Mao, W. Multi-operation multi-machine scheduling. HPCN-Europe 1995, 1995 Berlin, Heidelberg. Springer, Berlin, Heidelberg, 33-38.
12. Matta, M. E. 2009. A genetic algorithm for the proportionate multiprocessor open shop. Computers & Operations Research, 36, 2601-2618.
13. Naderi, B., Fatemi Ghomi, S. M. T., Aminnayeri, M. & Zandieh, M. 2011. Scheduling open shops with parallel machines to minimize total completion time. Journal of Computational and Applied Mathematics, 235, 1275-1287.
14. Ow, P. S. 1985. Focused Scheduling in Proportionate Flowshops. Management Science, 31, 852-869.
15. Pinedo, M. L. 2016. Scheduling: Theory, Algorithms, and Systems, Cham, Springer International Publishing.
16. Zhang, J., Wang, L. & Xing, L. 2019. Large-scale medical examination scheduling technology based on intelligent optimization. Journal of Combinatorial Optimization, 37, 385-404.