Algorithms for some maximization scheduling problems on a single machine. (English. Russian original) Zbl 1203.93126
Autom. Remote Control 71, No. 10, 2070-2084 (2010); translation from Avtom. Telemekh. 2010, No. 10, 63-79 (2010).
Summary: We consider two scheduling problems on a single machine, where a specific objective function has to be maximized in contrast to usual minimization problems. We propose exact algorithms for the single machine problem of maximizing total tardiness \(1 \| \max \sum T_j\) and for the problem of maximizing the number of tardy jobs \(1 \| \max \sum U_j\). In both cases, it is assumed that the processing of the first job starts at time zero and there is no idle time between the jobs. We show that problem \(1 \| \max \sum U_j\) is polynomially solvable. For several special cases of problem \(1 \| \max \sum T_j\), we present exact polynomial algorithms. Moreover, we give an exact pseudo-polynomial algorithm for the general case of the latter problem and an alternative exact algorithm.
MSC:
| 93C83 | Control/observation systems involving computers (process control, etc.) |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 49N90 | Applications of optimal control and differential games |
References:
| [1] | Moore, J.M., An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs, Manage. Sci., 1968, vol. 15, no. 1, pp. 102–109. · Zbl 0164.20002 · doi:10.1287/mnsc.15.1.102 |
| [2] | Du, J. and Leung, J. Y.-T., Minimizing Total Tardiness on One Processor is NP-hard, Math. Oper. Res., 1990, vol. 15, pp. 483–495. · Zbl 0714.90052 · doi:10.1287/moor.15.3.483 |
| [3] | Gafarov, E.P. and Lazarev, A.A., A Special Case of the Single-machine Total Tardiness Problem is NP-hard, Izv. Ross. Akad. Nauk, Teor. Sist. Upravlen., 2006, no. 3, pp. 120–128. · Zbl 1260.93116 |
| [4] | Lawler, E.L., A Pseudopolynomial Algorithm for Sequencing Jobs to Minimize Total Tardiness, Ann. Discret. Math., 1977, vol. 1, pp. 331–342. · Zbl 0353.68071 · doi:10.1016/S0167-5060(08)70742-8 |
| [5] | Szwarc, W., Della Croce, F., and Grosso, A., Solution of the Single Machine Total Tardiness Problem, J. Scheduling, 1999, vol. 2, pp. 55–71. · Zbl 0963.90029 · doi:10.1002/(SICI)1099-1425(199903/04)2:2<55::AID-JOS14>3.0.CO;2-5 |
| [6] | Potts, C.N. and Van Wassenhove, L.N., A Decomposition Algorithm for the Single Machine Total Tardiness Problem, Oper. Res. Lett., 1982, vol. 1, pp. 363–377. · Zbl 0508.90045 · doi:10.1016/0167-6377(82)90035-9 |
| [7] | Lazarev, A.A. and Gafarov, E.R., Teoriya raspisanii. Minimizatsiya summarnogo zapazdyvaniya dlya odnogo pribora (Scheduling Theory. Minimizing Total Delay for a Single Device), Moscow: Vychisl. Tsentr Ross. Akad. Nauk, 2006. |
| [8] | Lazarev, A., Dual of the Maximum Cost Minimization Problem, J. Math. Sci., 1989, vol. 44, no. 5, pp. 642–644. · Zbl 0665.90048 · doi:10.1007/BF01095176 |
| [9] | Huang, R.H. and Yang, C.L., Single-Machine Scheduling to Minimize the Number of Early Jobs, IEEE Int. Conf. Indust. Eng. Eng. Manage., 2007, art.no. 4419333, pp. 955–957. |
| [10] | Lazarev, A.A. and Werner, F., Algorithms for Special Cases of the Single Machine Total Tardiness Problem and an Application to the Even-Odd Partition Problem, Math. Comput. Modelling, 2009, vol. 49, no. 9–10, pp. 2061–2072. · Zbl 1198.68152 · doi:10.1016/j.mcm.2009.01.003 |
| [11] | Lazarev, A.A., Kvaratskhelia, A.G., and Gafarov, E.R., Algorithms for Solving the NP-Hard Problem of Minimizing Total Tardiness for a Single Machine, Dokl. Akad. Nauk, Math., 2007, vol. 412, no. 6, pp. 739–742. |
| [12] | Gafarov, E.R., Lazarev, A.A., and Werner, F., Algorithms for Maximizing the Number of Tardy Jobs or Total Tardiness on a Single Machine, Preprint of Otto-von-Guericke-Universität, Magdeburg, 2009, no. 38/09. |
| [13] | Lazarev, A.A. and Werner, F., A Graphical Realization of the Dynamic ProgrammingMethod for Solving NP-Hard Combinatorial Problems, Comput. Math. App., 2009, vol. 58, no. 4, pp. 619–631. · Zbl 1189.90186 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
