Maximizing total tardiness on a single machine in \(O(n^2)\) time via a reduction to half-product minimization. (English) Zbl 1332.90113
Summary: E. R. Gafarov et al. [Ann. Oper. Res. 196, 247–261 (2012; Zbl 1251.90143)] have recently presented an \(O(n^2)\) time dynamic programming algorithm for a single machine scheduling problem to maximize the total job tardiness. We reduce this problem in \(O(n\log n)\) time to a problem of unconstrained minimization of a function of 0-1 variables, called half-product, for which a simple \(O(n^2)\) time dynamic programming algorithm is known in the literature.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Citations:
Zbl 1251.90143References:
| [1] | Aloulou, M. A., Kovalyov, M. Y., & Portmann, M.-C. (2004). Maximization problems in single machine scheduling. Annals of Operations Research, 129(1-4), 21-32. · Zbl 1056.90050 · doi:10.1023/B:ANOR.0000030679.25466.02 |
| [2] | Aloulou, M. A., Kovalyov, M. Y., & Portmann, M.-C. (2007). Evaluating flexible solutions in single machine scheduling via objective function maximization: The study of computational complexity. RAIRO Operations Research, 41(1), 1-18. · Zbl 1377.90024 · doi:10.1051/ro:20070012 |
| [3] | Badics, T., & Boros, E. (1998). Minimization of half-products. Mathematics of Operations Research, 23(3), 649-660. · Zbl 0977.90026 · doi:10.1287/moor.23.3.649 |
| [4] | Can, A., & Ulusoy, G. (2014). Multi-project scheduling with two-stage decomposition. Annals of Operations Research, 217(1), 95-116. · Zbl 1303.90044 · doi:10.1007/s10479-014-1555-0 |
| [5] | Erel, E., & Ghosh, J. B. (2008). FPTAS for half-products minimization with scheduling applications. Discrete Applied Mathematics, 156(15), 3046-3056. · Zbl 1155.90379 · doi:10.1016/j.dam.2008.01.018 |
| [6] | Gafarov, E. R., Lazarev, A. A., & Werner, F. (2012). Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one. Annals of Operations Research, 196(1), 247-261. · Zbl 1251.90143 · doi:10.1007/s10479-011-1055-4 |
| [7] | Gafarov, E. R., Lazarev, A. A., & Werner, F. (2013). Single machine total tardiness maximization problems: Complexity and algorithms. Annals of Operations Research, 207(1), 121-136. · Zbl 1273.90079 · doi:10.1007/s10479-012-1288-x |
| [8] | Gawiejnowicz, S., & Kononov, A. (2014). Isomorphic scheduling problems. Annals of Operations Research, 213(1), 131-145. · Zbl 1296.90045 · doi:10.1007/s10479-012-1222-2 |
| [9] | Hashemian, N., Diallo, C., & Vizvári, B. (2014). Makespan minimization for parallel machines scheduling with multiple availability constraints. Annals of Operations Research, 213(1), 173-186. · Zbl 1296.90048 · doi:10.1007/s10479-012-1059-8 |
| [10] | Janiak, A., Kovalyov, M. Y., Kubiak, W., & Werner, F. (2005). Positive half-products and scheduling with controllable processing times. European Journal of Operational Research, 165(2), 416-422. · Zbl 1066.90031 · doi:10.1016/j.ejor.2004.04.012 |
| [11] | Jurisch, B., Kubiak, W., & Jozefowska, J. (1997). Algorithms for minclique scheduling problems. Discrete Applied Mathematics, 72(1-2), 115-139. · Zbl 0872.90048 · doi:10.1016/S0166-218X(96)00040-6 |
| [12] | Kellerer, H., & Strusevich, V. (2012). The symmetric quadratic knapsack problem: Approximation and scheduling applications. 4OR—A Quarterly Journal of Operations Research, 10(2), 111-161. · Zbl 1264.90001 · doi:10.1007/s10288-011-0180-x |
| [13] | Kellerer, H., & Strusevich, V. (2013). Fast approximation schemes for Boolean programming and scheduling problems related to positive convex half-product. European Journal of Operational Research, 228(1), 24-32. · Zbl 1332.90168 · doi:10.1016/j.ejor.2012.12.028 |
| [14] | Keshavarz, T., Salmasi, N., & Varmazyar, M. (2014). Minimizing total completion time in the flexible flowshop sequence-dependent group scheduling problem. Annals of Operations Research, 226(1), 351-377. · Zbl 1309.90027 |
| [15] | Kovalyov, M. Y., & Kubiak, W. (2012). A generic FPTAS for partition type optimization problems. International Journal of Planning and Scheduling, 1(3), 209-233. · doi:10.1504/IJPS.2012.050127 |
| [16] | Kubiak, W. (1995). New results on the completion time variance minimization. Discrete Applied Mathematics, 58(2), 157-168. · Zbl 0833.90070 · doi:10.1016/0166-218X(93)E0125-I |
| [17] | Kubiak, W. (2005). Minimization of ordered, symmetric half-products. Discrete Applied Mathematics, 146(3), 287-300. · Zbl 1084.90030 · doi:10.1016/j.dam.2004.07.007 |
| [18] | Lawler, E. L., & Moore, J. M. (1969). A functional equation and its application to resource allocation and sequencing problems. Management Science, 16(1), 77-84. · Zbl 0184.23303 · doi:10.1287/mnsc.16.1.77 |
| [19] | St. John, R., & Tóth, S. F. (2014). Spatially explicit forest harvest scheduling with difference equations. Annals of Operations Research, 232(1), 235-257. · Zbl 1323.90026 |
| [20] | Xu, Z. (2012). A strongly polynomial FPTAS for the symmetric quadratic knapsack problem. European Journal of Operational Research, 218(2), 377-381. · Zbl 1244.90202 · doi:10.1016/j.ejor.2011.10.049 |
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.
