İki kriterli tek makinalı çizelgeleme problemi için bir yaklaşım

Bu çalışmada, maksimum ağırlıklı geç bitirme ve ağırlıklı toplam akış zamanının en küçüklendiği iki kriterli tek makinalı çizelgeleme problemi için bir yaklaşım önerilmiştir. Tüm baskın noktaları üretebilen bu algoritma; aynı zamanda karar vericinin belirlediği bir kalite seviyesine göre baskın nokta kümesini temsil edebilen bir altküme bulmayı da garantilemektedir. Geliştirilen yaklaşım, farklı büyüklükteki ve farklı özelliklerdeki problemler üzerinde farklı kalite seviyelerinde uygulanmıştır. Deney sonuçları, algoritmamızın hem çözüm süresi hem karar vericiye sunulan çizelge sayısı açısından iyi bir yaklaşım olduğunu göstermektedir.

Anahtar Kelimeler:

iki kriterli tek makinalı çizelgeleme, maksimum ağırlıklı geç bitirme, ağırlıklı toplam akış zamanı, baskın nokta kümesi

PDF

___

1. Ehrgott, M. ve Gandibleux, X., A survey and annotated bibliography of multiobjective combinatorial optimization, OR Spektrum, 22, 425-460, 2000.
2. Dileepan, P. and Sen, T., Bicriterion static scheduling research for a single machine, Omega, 16 (1), 53-59, 1988.
3. Fry, T.D., Armstrong, R.D. ve Lewis, H., A framework for single machine multiple objective sequencing research, Omega, 17(6), 595-607, 1989.
4. Nagar, A., Haddock, J. ve Heragu, S., Multiple and bicriteria scheduling: A literature survey, European journal of operational research, 81 (1), 88-104, 1995.
5. Eren, T., ve Güner, E., Tek ve Paralel Makinalı Problemlerde Çok Ölçütlü Çizelgeleme problemleri için bir Literatür taraması, Gazi Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, 17 (4), 37-69, 2002.
6. Hoogeveen, H., Multicriteria scheduling, European Journal of Operational Research, 167(3), 592-623, 2005.
7. T’kindt V ve Billaut J-C, Multicriteria scheduling: theory, models and algorithms. Springer, Berlin, 2002.
8. Van Wassenhove, L. N., ve Gelders, F., Solving A Bicriterion Scheduling Problem, European Journal of Operational Research, 4 (1), 42-48, 1980.
9. Smith, W. E., Varios Optimizers for Single-Stage Production, Naval Research Logistics Quarterly, 3, 59-66, 1956.
10. Köksalan, M. ve Keha, A.B., Using genetic algorithms for single-machine bicriteria scheduling problems. European Journal of Operational Research, 145 (3), 543-556, 2003.
11. Huo, Y., Leung, J.Y.T. ve Zhao, H., Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness. European Journal of Operational Research, 177 (1), 116-134, 2007.
12. He, C., Lin, H. ve Wang, X., Single machine bicriteria scheduling with equal-length jobs to minimize total weighted completion time and maximum cost. 4OR, 12(1), 87-93, 2014.
13. Shabtay, D. ve Kaspi, M., Minimizing the total weighted flow time in a single machine with controllable processing times. Computers & Operations Research, 31(13), 2279-2289, 2004.
14. Sayın, S., Measuring the quality of discrete representations of efficient sets in multiple objective mathematical programming, Mathematical Programming, Ser. A 87, 543-560, 2000.
15. Wu, J. ve Azarm, S., Metrics for Quality Assessment of a Multiobjective Design Optimization Solution Set,” Journal of Mechanical Design, Transactions of the ASME, 123 (1), 18-25, 2001.
16. Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C. M., ve Grunert da Fonseca, V. Performance Assessment of Multiobjective Optimizers: An Analysis and Review, IEEE Transactions on Evolutionary Computation, 7 (2), 117-132, 2003.
17. Faulkenberg, S.L. ve Wiecek, M.M., On the quality of discrete representations in multiple objective programming. Optimization and Engineering, 11 (3), 423-440, 2010.
18. Sylva, J., Crema, A., A method for finding well-dispersed subsets of non-dominated vectors for multiple objective mixed integer linear programs,” European Journal of Operational Research, 180 (3), 1011-1027, 2007.
19. Masin, M. ve Bukchin, Y., Diversity Maximization Approach for Multiobjective Optimization,” Operations Research, 56 (2), 411-424, 2008.
20. Ceyhan, G., Köksalan, M. ve Lokman, B., “Finding a representative nondominated set for multi-objective mixed integer programs”, European Journal of Operational Research, 272(1), 61-77, 2019.
21. Baker, K.R. ve Martin, J.B., An experimental comparison of solution algorithms for the single machine tardiness problem, Naval Research Logistics Quarterly, 21, 187–200, 1974.
22. Rinnooy Kan, A.H.G., Lageweg, B.J. ve Lenstra, J.K., Minimizing total costs in one machine scheduling, Operations Research 23, 908-927, 1975.
23. Ow, P.S. ve Morton, T.E., The single machine early/tardy problem, Management Science 35 (2), 177-191, 1992.