Document Type : Research Paper
Authors
Abstract
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.
Keywords
Aryanezhad, M. B., Jabbarzadeh, A., & Zareei, A. (2009). Combination of Genetic Algorithm and LP-metric to solve single machine bi-criteria scheduling problem. Paper presented at the Industrial Engineering and Engineering Management, 2009. IEEM 2009. IEEE International Conference on.
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.
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.
)