EN|RU
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
Keywords: schedule, polytope, affine hull, support inequality. DOI: 10.33048/daio.2021.28.697 Ruslan Yu. Simanchev 1,2 Received July 14, 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). |
|
![]() |
|
© Sobolev Institute of Mathematics, 2015 | |
![]() |
|