The affine hull of the schedule polytope for servicing identical requests by parallel devices
Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 1, pp. 48-67.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. Tab. 1, illustr. 2, bibliogr. 20.
Keywords: schedule, polytope, affine hull, support inequality.
@article{DA_2021_28_1_a2,
     author = {R. Yu. Simanchev and P. V. Solovieva and I. V. Urazova},
     title = {The affine hull of the schedule polytope for servicing identical requests by parallel devices},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {48--67},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2021_28_1_a2/}
}
TY  - JOUR
AU  - R. Yu. Simanchev
AU  - P. V. Solovieva
AU  - I. V. Urazova
TI  - The affine hull of the schedule polytope for servicing identical requests by parallel devices
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2021
SP  - 48
EP  - 67
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2021_28_1_a2/
LA  - ru
ID  - DA_2021_28_1_a2
ER  - 
%0 Journal Article
%A R. Yu. Simanchev
%A P. V. Solovieva
%A I. V. Urazova
%T The affine hull of the schedule polytope for servicing identical requests by parallel devices
%J Diskretnyj analiz i issledovanie operacij
%D 2021
%P 48-67
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2021_28_1_a2/
%G ru
%F DA_2021_28_1_a2
R. Yu. Simanchev; P. V. Solovieva; I. V. Urazova. The affine hull of the schedule polytope for servicing identical requests by parallel devices. Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 1, pp. 48-67. http://geodesic.mathdoc.fr/item/DA_2021_28_1_a2/

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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

[5] Crowder H., Jonson E. L., Padberg M. W., “Solving large-scale zero-one linear programming problems”, Oper. Res., 31 (1983), 803–834 | DOI | Zbl

[6] Grötschel M., Holland O., “Solution of large-scale symmetric travelling salesman problems”, Math. Program., 51 (1991), 141–202 | DOI | MR | Zbl

[7] Grötschel M., Wakabayashi Y., “A cutting plane algorithm for a clustering problem”, Math. Program., 45 (1989), 59–96 | DOI | MR | Zbl

[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 | DOI | MR

[9] Mokotoff E., “An exact algorithm for the identical parallel machine scheduling problem”, Eur. J. Oper. Res., 152 (2004), 758–769 | DOI | MR | Zbl

[10] Queyranne M., “Structure of simple scheduling polyhedron”, Math. Program., 58 (1993), 263–285 | DOI | MR | Zbl

[11] Queyranne M., Wang Y., “Single-machine scheduling polyhedra with precedence constraints”, Math. Oper. Res., 16 (1991), 1–20 | DOI | MR | Zbl

[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 | MR

[13] Schulz A. S., Polytopes and scheduling, PhD thesis, Technische Univ. Berlin, Berlin, 1996 | Zbl

[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) | MR | Zbl

[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) | MR | Zbl

[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) | MR | Zbl

[18] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979 | MR | Zbl

[19] N. Christofides, Graph Theory: An Algorithmic Approach, Academic Press, New York, 1975 | MR | Zbl

[20] Brucker P., Knust S., Complexity results for scheduling problems, Univ. Osnabrück, Osnabrück, 2009 (accessed Oct. 23, 2020) www2.informatik.uni-osnabrueck.de/knust/class | MR