نوع مقاله : مقاله پژوهشی
نویسندگان
دانشگاه علامه طباطبائی
چکیده
مسائ عملی زمانبندی معمولاً تصمیمگیرنده را وادار به در نیر گرفتن تعداد زیادی از معیارها قب از اتخار
تصمیم می نمایند. این تحیید یک مسئله زمانبندی تک ماشین را مورد بررسی قرار می دهد که هدف در آن
حداق کردن ترکیبی از دو معیار دیرکرد ک و واریانا زمان انتیار می باشد به حوری که زمان بیکاری در
ماشین مجاز نیست. حداق کردن دیرکرد ک همیشه به عنوان یک معیار عملکرد مهم در سیستم های عملی،
که می توان با استفاده از آن از تحمی هزینههای جریمه دیرکرد اجتناب نمود، مطرح می باشد و واریانا زمان
انتیار نیز یک معیار مهم در پیادهسازی کیفیت هدمات ) QoS ( در بسیاری از سیستم ها می باشد. هر کدام از
این دو معیار از نوع NP-hard می باشند و بنابراین ترکیب هطی آن ها نیز NP-hard هواهد بود. برای این
مسئله الگوریتمی ژنتیک حراحی شده که از ساهتار معمول آن استفاده می کند. دو نوع جمعیت هیوریستیک و
تصادفی برای جمعیت اولیه و دو نوع تابع برازش در الگوریتم به کار رفته است. کارایی الگوریتم ژنتیک ارائه
شده به وسیله تست روی تعداد زیادی از مسائ نشان داده می شود
کلیدواژه‌ها
عنوان مقاله [English]
Bicriteria single machine scheduling to minimize total tardiness and waiting time variance by genetic algorithms
نویسندگان [English]
- Maghsoud Amiri
- Mahdi Keshavarz Gharabaei
چکیده [English]
Actual scheduling problems may necessitate the decision maker to consider a variety of criteria prior to make any decision. This research considers a single machine scheduling problem, with the objective of minimizing a combination of total tardiness and waiting time variance criteria in which the idle time is not allowed. Minimizing total tardiness is always regarded as one of the most important performance criteria in practical systems to avoid penalty costs of tardiness and waiting time variance is an important criterion in establishing Quality of Service (QoS) in many systems. Each of these criteria is known to be NP-hard and therefore the linear combination of them will be NP-hard as well. For this problem, we developed a genetic algorithm by utilizing its general structure. Two types of heuristic and random initial population and two distinct fitness functions are applied to genetic algorithms. The GA is shown experimentally to perform well by testing on various instances.
کلیدواژه‌ها [English]
- Bicriteria scheduling
- Single machine
- Genetic Algorithms
- Total tardiness
- Waiting time variance
Bagchi, U. (1989). Simultaneous Minimization of Mean and Variation of Flow Time and Waiting Time in Single Machine Systems. Operations Research, 37(1), 118-125.
Bagchi, U., Sullivan, R. S., & Chang, Y.-L. (1987). Minimizing Mean Squared Deviation of Completion Times about a Common Due Date. Management Science, 33(7), 894-906.
Baker, K. R., & Trietsch, D. (2009). Principles of Sequencing and Scheduling: John Wiley & Sons.
Deb, K. (2009). Multi-Objective Optimization Using Evolutionary Algorithms: John Wiley & Sons.
Du, J., & Leung, J. Y. T. (1990). Minimizing Total Tardiness on One Machine Is NP-Hard. Mathematics of Operations Research, 15(3), 483-495.
Eilon, S., & Chowdhury, I. G. (1977). Minimising Waiting Time Variance in the Single Machine Problem. Management Science, 23(6), 567-575.
Ferrolho, A., & Crisostomo, M. (2006). Genetic Algorithm for the Single Machine Total Weighted Tardiness Problem. Paper presented at the E-Learning in Industrial Electronics, 2006 1ST IEEE International Conference on.
F , T. ., , ., a l , ., F a , . 1989 . A l T a l a h . The Journal of the Operational Research Society, 40(3), 293-297.
071 مطالعات مدیریت صنعتی، سال سیزدهم، شماره 63 ، بهار 49
Gupta, M. C., Gupta, Y. P., & Bector, C. R. (1990). Minimizing the Flow-Time Variance in Single-Machine Systems. The Journal of the Operational Research Society, 41(8), 767-779.
Han, H. (2005). Multicriteria scheduling. European Journal of Operational Research, 167(3), 592-623.
Holsenback, J. E., & Russell, R. M. (1992). A Heuristic Algorithm for Sequencing on One Machine to Minimize Total Tardiness. The Journal of the Operational Research Society, 43(1), 53-62.
Jolai, F., Rabbani, M., Amalnick, S., Dabaghi, A., Dehghan, M., & Parast, M. Y. (2007). Genetic algorithm for bi-criteria single machine scheduling problem of minimizing maximum earliness and number of tardy jobs. Applied Mathematics and Computation, 194(2), 552-560.
Kanet, J. J. (1981). Minimizing Variation of Flow Time in Single Machine Systems. Management Science, 27(12), 1453-1459.
Köksalan, M., & Burak Keha, A. (2003). Using genetic algorithms for single-machine bicriteria scheduling problems. European Journal of Operational Research, 145(3), 543-556.
Koulamas, C. (1994). The Total Tardiness Problem: Review and Extensions. Operations Research, 42(6), 1025-1041.
Madureira, A., Ramos, C., & do Carmo Silva, S. (2001). A GA based scheduling system for dynamic single machine problem. Paper presented at the Assembly and Task Planning, 2001, Proceedings of the IEEE International Symposium on.
Merten, A. G., & Muller, M. E. (1972). Variance Minimization in Single Machine Sequencing Problems. Management Science, 18(9), 518-528.
زمانبندی دو معیاره برای حداقل سازی زمان دیرکرد کل و واریانس زمان انتظار بر روی ... 191
Morton, T. E., Rachamadugu, R. V., & Vepsalainen, A. (1984). Accurate myopic heuristics for tardiness scheduling (GSIA technical report ed.): Carnegie-Mellon University.
Panneerselvam, R. (2006). Simple heuristic to minimize total tardiness in a single machine scheduling problem. The International Journal of Advanced Manufacturing Technology, 30(7), 722-726.
Pinedo, M. (2008). Scheduling: Theory, Algorithms, and Systems: Springer.
Potts, C. N., & Van Wassenhove, L. N. (1982). A decomposition algorithm for the single machine total tardiness problem. Operations Research Letters, 1(5), 177-181.
Potts, C. N., & Van Wassenhove, L. N. (1991). Single Machine Tardiness Sequencing Heuristics. IIE Transactions, 23(4), 346-354.
Srirangacharyulu, B., & Srinivasan, G. (2010). Completion time variance minimization in single machine and multi-machine systems. Computers & Operations Research, 37(1), 62-71.
Su, L.-H., & Tien, Y.-Y. (2011). Minimizing mean absolute deviation of completion time about a common due window subject to maximum tardiness for a single machine. International Journal of Production Economics, 134(1), 196-203.
Tan, K. C., Khor, E. F., & Lee, T. H. (2005). Multiobjective evolutionary algorithms and applications: Springer.
Wieslaw, K. (1993). Completion time variance minimization on a single machine is difficult. Operations Research Letters, 14(1), 49-59.
Ye, N., Li, X., Farley, T., & Xu, X. (2007). Job scheduling methods for reducing waiting time variance. Computers & Operations Research, 34(10), 3069-3083.
Yoon, S. H., & Lee, I. S. (2011). New constructive heuristics for the total weighted tardiness problem. J Oper Res Soc, 62(1), 232-237.
)