Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2021, 15:1, 146-157
Volume 28, No 1, 2021, P. 48-67
UDC 519.1+519.8
R. Yu. Simanchev, P. V. Solovieva, and I. V. Urazova
The affine hull of the schedule polytope for servicing identical requests by parallel devices
Abstract:
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.
DOI: 10.33048/daio.2021.28.697
Ruslan Yu. Simanchev 1,2
Polina V. Solovieva 1
Inna V. Urazova 1
1. Dostoevsky Omsk State University,
55a Mir Avenue, 644077 Omsk, Russia
2. Omsk Scientific Center of SB RAS,
15 Karl Marx Avenue, 644024 Omsk, Russia
e-mail: osiman@rambler.ru, polinochka.chervonnykh@mail.ru, urazovainn@mail.ru
Received July 14, 2020
Revised September 27, 2020
Accepted September 28, 2020
References
[1] R. Yu. Simanchev and I. V. Urazova, An integer-valued model for the problem of minimizing the total servicing time of unit claims with parallel devices with precedences, Avtom. Telemekh., No. 10, 100–106 (2010) [Russian] [Autom. Remote Control 71 (10), 2102–2108 (2010)].[2] R. Yu. Simanchev, I. V. Urazova, and A. Yu. Kochetov, The branch and cut method for the clique partitioning problem, Diskretn. Anal. Issled. Oper. 26 (3), 60–87 (2019) [Russian] [J. Appl. Ind. Math. 13 (3), 539–556 (2019)].
[3] D. L. Applegate, R. E. Bixby, V. Chvátal, W. J. Cook, D. G. Espinoza, M. Goycoolea, and K. Helsgaun, Certification of an optimal TSP tour through 85,900 cities, Oper. Res. Lett. 37, 11–15 (2009).
[4] W. H. Bouma and B. Goldengorin, A polytime algorithm based on a primal LP model for the scheduling problem 1|$pmtn$; $p_j = 2$; $r_j |\sum w_j C_j$ , in Recent Advances in Applied Mathematics (Proc. Amer. Conf. Appl. Math., Cambridge, MA, USA, Jan. 27–29, 2010) (WSEAS Press, Stevens Point, 2010), pp. 415–420.
[5] H. Crowder, E. L. Jonson, and M. W. Padberg, Solving large-scale zero-one linear programming problems, Oper. Res. 31, 803–834 (1983).
[6] M. Grötschel and O. Holland, Solution of large-scale symmetric travelling salesman problems, Math. Program. 51, 141–202 (1991).
[7] M. Grötschel and Y. Wakabayashi, A cutting plane algorithm for a clustering problem, Math. Program. 45, 59–96 (1989).
[8] E. Balas, On the facial structure of scheduling polyhedra, in Mathematical Programming Essays in Honor of George B. Dantzig, Pt. I (North-Holland, Amsterdam, 1985), pp. 179–218 (Math. Program. Studies, Vol. 24).
[9] E. Mokotoff, An exact algorithm for the identical parallel machine scheduling problem, Eur. J. Oper. Res. 152, 758–769 (2004).
[10] M. Queyranne, Structure of simple scheduling polyhedron, Math. Program. 58, 263–285 (1993).
[11] M. Queyranne and Y. Wang, Single-machine scheduling polyhedra with precedence constraints, Math. Oper. Res. 16, 1–20 (1991).
[12] G. L. Nemhauser and M. W. P. Savelsbergh, A cutting plane algorithm of single machine scheduling problem with release times, in Combinatorial Optimization: New Frontiers in Theory and Practice (Springer, Heidelberg, 1992), pp. 63–84 (NATO ASI Ser., Vol. 82).
[13] A. S. Schulz, Polytopes and scheduling, PhD Thesis (Technische Univ. Berlin, Berlin, 1996).
[14] M. Queyranne and A. S. Schulz, Polyhedral Approaches to Machine Scheduling (Technische Univ. Berlin, Berlin, 1994).
[15] R. Yu. Simanchev and I. V. Urazova, Scheduling unit-time jobs on parallel processors polytope, Diskretn. Anal. Issled. Oper. 18 (1), 85–97 (2011) [Russian].
[16] R. Yu. Simanchev and N. Yu. Shereshik, Integer models for the interruptoriented services of jobs by single machine, Diskretn. Anal. Issled. Oper. 21 (4), 89–101 (2014) [Russian].
[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), 78–90 (2015) [Russian].
[18] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979; Mir, Moscow, 1982 [Russian]).
[19] N. Christofides, Graph Theory: An Algorithmic Approach (Academic Press, New York, 1975; Mir, Moscow, 1978 [Russian]).
[20] P. Brucker and S. Knust, Complexity Results for Scheduling Problems (Univ. Osnabrück, Osnabrück, 2009). Available at www2.informatik.uni-osnabrueck.de/knust/class (accessed Oct. 23, 2020).
