The affine hull of the schedule polytope for servicing identical requests by parallel devices. (Russian. English summary) Zbl 1497.90100
Summary: Under consideration are some polyhedral properties of the set of schedules for servicing identical requests by parallel devices. The requests satisfy some precedence conditions. Any service interruptions are prohibited. We propose some formalization of the set of schedules as a family of subsets of a finite set, define the polytope of schedules, and find the affine hull and dimension of this polytope. We also obtain the conditions under which the inequalities determining its polyhedral relaxation are the support inequalities.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 52B12 | Special polytopes (linear programming, centrally symmetric, etc.) |
References:
| [1] | R. Yu. Simanchev, I. V. Urazova, “An integer-valued model for the problem of minimizing the total servicing time of unit claims with parallel devices with precedences”, Autom. Remote Control, 71:10 (2010), 2102-2108 · Zbl 1218.93055 · doi:10.1134/S0005117910100097 |
| [2] | R. Yu. Simanchev, I. V. Urazova, A. Yu. Kochetov, “The branch and cut method for the clique partitioning problem”, J. Appl. Ind. Math., 13:3 (2019), 539-556 · Zbl 1438.90395 · doi:10.1134/S1990478919030153 |
| [3] | Applegate D. L., Bixby R. E., Chvátal V., Cook W. J., Espinoza D. G., Goycoolea M., Helsgaun K., “Certification of an optimal TSP tour through 85 900 cities”, Oper. Res. Lett., 37 (2009), 11-15 · Zbl 1154.90601 · doi:10.1016/j.orl.2008.09.006 |
| [4] | Bouma W. H., Goldengorin B., “A polytime algorithm based on a primal LP model for the scheduling problem \(1|pmtn;p_j=2;r_j|\sum w_jC_j\)”, Recent Advances in Applied Mathematics, Proc. Amer. Conf. Appl. Math. (Cambridge, MA, USA, Jan. 27-29, 2010), WSEAS Press, Stevens Point, 2010, 415-420 · Zbl 1341.90039 |
| [5] | Crowder H., Jonson E. L., Padberg M. W., “Solving large-scale zero-one linear programming problems”, Oper. Res., 31 (1983), 803-834 · Zbl 0576.90065 · doi:10.1287/opre.31.5.803 |
| [6] | Grötschel M., Holland O., “Solution of large-scale symmetric travelling salesman problems”, Math. Program., 51 (1991), 141-202 · Zbl 0733.90047 · doi:10.1007/BF01586932 |
| [7] | Grötschel M., Wakabayashi Y., “A cutting plane algorithm for a clustering problem”, Math. Program., 45 (1989), 59-96 · Zbl 0675.90072 · doi:10.1007/BF01589097 |
| [8] | Balas E., “On the facial structure of scheduling polyhedra”, Mathematical Programming Essays in Honor of George B. Dantzig, v. I, Math. Program. Studies, 24, North-Holland, Amsterdam, 1985, 179-218 · Zbl 0582.90053 · doi:10.1007/BFb0121051 |
| [9] | Mokotoff E., “An exact algorithm for the identical parallel machine scheduling problem”, Eur. J. Oper. Res., 152 (2004), 758-769 · Zbl 1043.90030 · doi:10.1016/S0377-2217(02)00726-9 |
| [10] | Queyranne M., “Structure of simple scheduling polyhedron”, Math. Program., 58 (1993), 263-285 · Zbl 0778.90031 · doi:10.1007/BF01581271 |
| [11] | Queyranne M., Wang Y., “Single-machine scheduling polyhedra with precedence constraints”, Math. Oper. Res., 16 (1991), 1-20 · Zbl 0747.90051 · doi:10.1287/moor.16.1.1 |
| [12] | Nemhauser G. L., Savelsbergh M. W. P., “A cutting plane algorithm of single machine scheduling problem with release times”, Combinatorial Optimization: New Frontiers in Theory and Practice, NATO ASI Ser., 82, Springer, Heidelberg, 1992, 63-84 · Zbl 0768.90040 |
| [13] | Schulz A. S., Polytopes and scheduling, PhD thesis, Technische Univ. Berlin, Berlin, 1996 · Zbl 0859.90088 |
| [14] | Queyranne M., Schulz A. S., Polyhedral approaches to machine scheduling, Technische Univ. Berlin, Berlin, 1994 |
| [15] | R. Yu. Simanchev, I. V. Urazova, “Scheduling unit-time jobs on parallel processors polytope”, Diskretn. Anal. Issled. Oper., 18:1 (2011), 85-97 (Russian) · Zbl 1249.90079 |
| [16] | R. Yu. Simanchev, N. Yu. Shereshik, “Integer models for the interrupt-oriented services of jobs by single machine”, Diskretn. Anal. Issled. Oper., 21:4 (2014), 89-101 (Russian) · Zbl 1324.90064 |
| [17] | N. Yu. Shereshik, “Relaxations for the polyhedron of optimal schedules for the problem of interrupt-oriented service of jobs with a single machine”, Diskretn. Anal. Issled. Oper., 22:6 (2015), 78-90 (Russian) · Zbl 1349.90396 |
| [18] | M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979 · Zbl 0411.68039 |
| [19] | N. Christofides, Graph Theory: An Algorithmic Approach, Academic Press, New York, 1975 · Zbl 0321.94011 |
| [20] | Brucker P., Knust S., Complexity results for scheduling problems, Univ. Osnabrück, Osnabrück, 2009 · Zbl 0946.90026 |
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.
