ENRU  
Volume 22, No 6, 2015, P. 78–90 UDC 519.1
Keywords: scheduling theory, integer programming model, polytope, polyhedron, valid inequality, relaxation. DOI: 10.17377/daio.2015.22.486 Nikolay Yu. Shereshik ^{1} Received 11 April 2015 References[1] Ph. Baptiste, J. Carlier, A. V. Kononov, M. Queyranne, S. V. Sevastyanov, and M. I. Sviridenko, Structural properties of optimal schedules with preemption, Diskretn. Anal. Issled. Oper., 16, No. 1, 3–36, 2009. Translated in J. Appl. Ind. Math., 4, No. 4, 455–474, 2010.[2] A. A. Lazarev and A. G. Kvaratskhelia, Properties of optimal schedules for the minimization total weighted completion time in preemptive equallength job with release dates scheduling problem on a single machine, Avtom. Telemekh., No. 10, 80–89, 2010. Translated in Autom. Remote Control, 71, No. 10, 2085–2092, 2010. [3] R. Yu. Simanchev and N. Yu. Shereshik, Use of dichotomy scheme for minimum directive algorithm in various requirements satisfaction by single machine, Vestn. Omsk. Univ., No. 2, 48–50, 2013. [4] R. Yu. Simanchev and N. Yu. Shereshik, Integer models for the interruptoriented services of jobs by single machine, Diskretn. Anal. Issled. Oper., 21, No. 4, 89–101, 2014. [5] H. W. Bouma and B. Goldengorin, A polytime algorithm based on a primal LP model for the scheduling problem 1pmtn; p_{i} = 2; r_{i} Σ ω_{i}C_{i} , in Recent Advances in Applied Mathematics (Proc. 2010 Am. Conf. Appl. Math., Cambridge, USA, Jan. 27–29, 2010), pp. 415–420, WSEAS Press, Stevens Point, USA, 2010. [6] P. Brucker and S. Knust, Complexity results for scheduling problems, Available at http://www.informatik.uniosnabrueck.de/knust/class/. Accessed Oct. 13, 2015. 

© Sobolev Institute of Mathematics, 2015  