Volume 22, No 6, 2015, P. 78–90
UDC 519.1
N. Yu. Shereshik
Relaxation for the polyhedron of optimal schedules for the problem of interrupt-oriented service of jobs with a single machine
Abstract:
We consider the problem of minimizing the total service time of different jobs from one device preemption. We construct two classes of hyperplanes containing polyhedron of optimal schedules for this problem and describe computer experiments.
Ill. 4, tab. 1, bibliogr. 6.
Keywords: scheduling theory, integer programming model, polytope, polyhedron, valid inequality, relaxation.
DOI: 10.17377/daio.2015.22.486
Nikolay Yu. Shereshik 1
1. Omsk State University,
55-a Mir Ave., 644077 Omsk, Russia
e-mail: m-m_pikm@mail.ru
Received 11 April 2015
Revised 16 August 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 equal-length 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 interrupt-oriented 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 1|pmtn; pi = 2; ri| Σ ωiCi , 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.uni-osnabrueck.de/knust/class/. Accessed Oct. 13, 2015.
