On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems. (English) Zbl 1146.90032
Summary: Enumerative approaches to solving optimization problems, such as branch and bound, require a subroutine that produces a lower bound on the value of the optimal solution. In the domain of scheduling problems the requisite lower bound has typically been derived from either the solution to a linear-programming (LP) relaxation of the problem or the solution to a combinatorial relaxation. In this paper we investigate, from a theoretical perspective, the relationship between several LP-based lower bounds and combinatorial lower bounds for three scheduling problems in which the goal is to minimize the average weighted completion time of the jobs scheduled.
We establish a number of facts about the relationship between these different sorts of lower bounds, including the equivalence of certain LP-based lower bounds for these problems to combinatorial lower bounds used in successful branch-and-bound algorithms. As a result, we obtain the first worst-case analysis of the quality of the lower bounds delivered by these combinatorial relaxations.
We establish a number of facts about the relationship between these different sorts of lower bounds, including the equivalence of certain LP-based lower bounds for these problems to combinatorial lower bounds used in successful branch-and-bound algorithms. As a result, we obtain the first worst-case analysis of the quality of the lower bounds delivered by these combinatorial relaxations.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C27 | Combinatorial optimization |
| 90C05 | Linear programming |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
References:
| [1] | F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, M. Sviridenko, Approximation schemes for minimizing average weighted completion time with release dates, in: Proc. 40th Annu. Symp. on Foundations of Computer Science, 1999, pp. 32-43.; F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, M. Sviridenko, Approximation schemes for minimizing average weighted completion time with release dates, in: Proc. 40th Annu. Symp. on Foundations of Computer Science, 1999, pp. 32-43. |
| [2] | Belouadah, H.; Posner, M. E.; Potts, C. N., Scheduling with release dates on a single machine to minimize total weighted completion time, Discrete Appl. Math., 36, 213-231 (1992) · Zbl 0757.90032 |
| [3] | Bianco, L.; Ricciardelli, S., Scheduling of a single machine to minimize total weighted completion time subject to release dates, Naval Res. Logist. Quart., 29, 151-167 (1982) · Zbl 0539.90044 |
| [4] | Chakrabarti, S.; Phillips, C.; Schulz, A. S.; Shmoys, D. B.; Stein, C.; Wein, J., Improved bounds on relaxations of a parallel machine scheduling problem, J. Combin. Optim., 1, 4, 413-426 (1998), (Preliminary version appeared in the Proc. 1996 Internat. Colloq. Automata, Languages and Programming) · Zbl 0911.90219 |
| [5] | Chandra, R., On \(n / 1 / \overline{F}\) dynamic deterministic systems, Naval Res. Logist. Quart., 26, 537-544 (1979) · Zbl 0496.90044 |
| [6] | Chekuri, C.; Motwani, R.; Natarajan, B.; Stein, C., Approximation techniques for average completion time scheduling, SIAM J. Comput., 31, 1, 146-166 (2000), (Preliminary version appeared in Proc. of the Eighth ACM-SIAM Symp. on Discrete Algorithms, 1997) · Zbl 0992.68066 |
| [7] | Chudak, F., A min-sum 1.5-approximation algorithm for scheduling unrelated parallel machines, J. Scheduling, 2, 2, 73-77 (1999) · Zbl 0963.90028 |
| [8] | Dessouky, M. I.; Deogun, J. S., Sequencing jobs with unequal ready times to minimize mean flow time, SIAM J. Comput., 10, 192-202 (1981) · Zbl 0454.68010 |
| [9] | Dyer, M. E.; Wolsey, L. A., Formulating the single machine sequencing problem with release dates as a mixed integer program, Discrete Appl. Math., 26, 255-270 (1990) · Zbl 0694.90060 |
| [10] | Eastman, W. L.; Even, S.; Isaacs, I. M., Bounds for the optimal scheduling of \(n\) jobs on \(m\) processors, Manage. Sci., 11, 2, 268-279 (1964) |
| [11] | M. Goemans, A supermodular relaxation for scheduling with release dates, in: Proc. Fifth MPS Conf. on Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 1084, Springer, Berlin, June 1996, pp. 288-300.; M. Goemans, A supermodular relaxation for scheduling with release dates, in: Proc. Fifth MPS Conf. on Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 1084, Springer, Berlin, June 1996, pp. 288-300. · Zbl 1414.90149 |
| [12] | M. Goemans, Improved approximation algorithms for scheduling with release dates, in: Proc. Eighth ACM-SIAM Symp. on Discrete Algorithms, 1997, pp. 591-598.; M. Goemans, Improved approximation algorithms for scheduling with release dates, in: Proc. Eighth ACM-SIAM Symp. on Discrete Algorithms, 1997, pp. 591-598. · Zbl 1321.68502 |
| [13] | Goemans, M.; Queyranne, M.; Schulz, A.; Skutella, M.; Wang, Y., Single machine scheduling with release dates, SIAM J. Discrete Math., 15, 165-192 (2002) · Zbl 1009.90096 |
| [14] | Goemans, M. X.; Williamson, D. P., Two-dimensional Gantt charts and a scheduling algorithm of Lawler, SIAM J. Discrete Math., 13, 281-294 (2000), (A preliminary version of this paper appeared in the Proc. Tenth ACM-SIAM Symp. on Discrete Algorithms, 1999) · Zbl 1054.90032 |
| [15] | L.A. Hall, Approximation algorithms for scheduling, in: D.S. Hochbaum (Ed.), Approximation Algorithms for NP-hard Problems, PWS Publishing Company, MA, 1997, pp. 1-43.; L.A. Hall, Approximation algorithms for scheduling, in: D.S. Hochbaum (Ed.), Approximation Algorithms for NP-hard Problems, PWS Publishing Company, MA, 1997, pp. 1-43. |
| [16] | Hall, L. A.; Schulz, A. S.; Shmoys, D. B.; Wein, J., Scheduling to minimize average completion time: off-line and on-line approximation algorithms, Math. Oper. Res., 3, 513-544 (1997) · Zbl 0883.90064 |
| [17] | Hariri, A. M.A.; Potts, C. N., An algorithm for single machine sequencing with release dates to minimize total weighted completion time, Discrete Appl. Math., 5, 99-109 (1983) · Zbl 0498.90044 |
| [18] | Phillips, C.; Stein, C.; Wein, J., Minimizing average completion time in the presence of release dates, Math. Programming B, 82, 199-224 (1998) · Zbl 0920.90074 |
| [19] | Potts, C. N.; Van Wassenhove, L. N., An algorithm for single machine sequencing with deadlines to minimize total weighted completion time, European J. Oper. Res., 12, 379-387 (1983) · Zbl 0496.90048 |
| [20] | Queyranne, M., Structure of a simple scheduling polyhedron, Math. Programming, 58, 263-285 (1993) · Zbl 0778.90031 |
| [21] | M. Queyranne, A.S. Schulz, Polyhedral approaches to machine scheduling, Technical Report 408/1994, Technical University of Berlin, 1994.; M. Queyranne, A.S. Schulz, Polyhedral approaches to machine scheduling, Technical Report 408/1994, Technical University of Berlin, 1994. |
| [22] | G. Rinaldi, A. Sassano, On a job scheduling problem with different ready times: some properties and a new algorithm to determine the optimal solution, Technical Report R.77-24, Istituto di Automatica, Università di Roma, Roma, 1977.; G. Rinaldi, A. Sassano, On a job scheduling problem with different ready times: some properties and a new algorithm to determine the optimal solution, Technical Report R.77-24, Istituto di Automatica, Università di Roma, Roma, 1977. |
| [23] | A.S. Schulz, Scheduling and polytopes, Ph.D. Thesis, Technical University of Berlin, Berlin, Germany, 1996.; A.S. Schulz, Scheduling and polytopes, Ph.D. Thesis, Technical University of Berlin, Berlin, Germany, 1996. · Zbl 0859.90088 |
| [24] | A.S. Schulz, M. Skutella, Random-based scheduling: new approximations and LP lower bounds, in: J. Rolim (Ed.), Randomization and Approximation Techniques in Computer Science, Lecture Notes in Computer Science, Vol. 1269, Springer, Berlin, 1997, pp. 119-133 (Proc. Internat. Workshop RANDOM’97).; A.S. Schulz, M. Skutella, Random-based scheduling: new approximations and LP lower bounds, in: J. Rolim (Ed.), Randomization and Approximation Techniques in Computer Science, Lecture Notes in Computer Science, Vol. 1269, Springer, Berlin, 1997, pp. 119-133 (Proc. Internat. Workshop RANDOM’97). |
| [25] | A.S. Schulz, M. Skutella, Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria, in: R. Burkard, G. Woeginger (Eds.), Algorithms—ESA’97, Lecture Notes in Computer Science Vol. 1284, Springer, Berlin, 1997, pp. 416-429 (Proc. Fifth Annu. European Symp. on Algorithms).; A.S. Schulz, M. Skutella, Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria, in: R. Burkard, G. Woeginger (Eds.), Algorithms—ESA’97, Lecture Notes in Computer Science Vol. 1284, Springer, Berlin, 1997, pp. 416-429 (Proc. Fifth Annu. European Symp. on Algorithms). · Zbl 1479.90111 |
| [26] | Smith, W. E., Various optimizers for single-stage production, Naval Res. Logist. Quart., 3, 59-66 (1956) |
| [27] | De Sousa, J. P.; Wolsey, L. A., A time-indexed formulation of non-preemptive single-machine scheduling problems, Math. Programming, 54, 353-367 (1992) · Zbl 0768.90041 |
| [28] | M. Van den Akker, LP-based solution methods for single-machine scheduling problems, Ph.D. Thesis, Eindhoven University of Technology, Eindhoven, Netherlands, 1994.; M. Van den Akker, LP-based solution methods for single-machine scheduling problems, Ph.D. Thesis, Eindhoven University of Technology, Eindhoven, Netherlands, 1994. · Zbl 0828.90059 |
| [29] | Van den Akker, M.; Van Hoesel, C. P.M.; Savelsbergh, M. W.P., A polyhedral approach to single-machine scheduling problems, Math. Programming, 85, 541-572 (1999) · Zbl 1072.90523 |
| [30] | Van den Akker, M.; Hurkens, C. A.J.; Savelsbergh, M. W.P., A time-indexed formulation for single-machine scheduling problems: column generation, INFORMS J. Comput., 12, 111-124 (2000) · Zbl 1034.90004 |
| [31] | Webster, S., New bounds for the identical parallel processor weighted flow time problem, Manage. Sci., 38, 1, 124-136 (1992) · Zbl 0777.90020 |
| [32] | L.A. Wolsey, Mixed integer programming formulations for production planning and scheduling problems, invited talk at the 12th Internat. Symp. on Mathematical Programming, MIT, Cambridge, 1985.; L.A. Wolsey, Mixed integer programming formulations for production planning and scheduling problems, invited talk at the 12th Internat. Symp. on Mathematical Programming, MIT, Cambridge, 1985. |
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.
