Geodesic
Relaxations for the polyhedron of optimal schedules for the problem of interrupt-oriented service of jobs with a~single machine
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 6, pp. 78-90.

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

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. 
@article{DA_2015_22_6_a4,
     author = {N. Yu. Shereshik},
     title = {Relaxations for the polyhedron of optimal schedules for the problem of interrupt-oriented service of jobs with a~single machine},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {78--90},
     publisher = {mathdoc},
     volume = {22},
     number = {6},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_6_a4/}
}
TY  - JOUR
AU  - N. Yu. Shereshik
TI  - Relaxations for the polyhedron of optimal schedules for the problem of interrupt-oriented service of jobs with a~single machine
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 78
EP  - 90
VL  - 22
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_6_a4/
LA  - ru
ID  - DA_2015_22_6_a4
ER  - 
%0 Journal Article
%A N. Yu. Shereshik
%T Relaxations for the polyhedron of optimal schedules for the problem of interrupt-oriented service of jobs with a~single machine
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 78-90
%V 22
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_6_a4/
%G ru
%F DA_2015_22_6_a4
N. Yu. Shereshik. Relaxations for the polyhedron of optimal schedules for the problem of interrupt-oriented service of jobs with a~single machine. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 6, pp. 78-90. http://geodesic.mathdoc.fr/item/DA_2015_22_6_a4/

[1] Ph. Baptiste, J. Carlier, A. V. Kononov, M. Queyranne, S. V. Sevastyanov, M. I. Sviridenko, “Structural properties of optimal schedules with preemption”, J. Appl. Ind. Math., 4:4 (2010), 455–474 | DOI | MR | Zbl

[2] A. A. Lazarev, 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”, Autom. Remote Control, 71:10 (2010), 2085–2092 | DOI | MR | Zbl

[3] R. Yu. Simanchev, N. Yu. Shereshik, “Use of dichotomy scheme for minimum directive algorithm in various requirements satisfaction by single machine”, Vestn. Omsk. Univ., 2013, no. 2, 48–50

[4] 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 | MR | Zbl

[5] Bouma W. H., Goldengorin B., “A polytime algorithm based on a primal LP model for scheduling problem $1|pmtn;p_i=2;r_i|\sum\omega_i C_i$”, Recent Advances in Applied Mathematics, Proc. Amer. Conf. Appl. Math. AMERICAN-MATH'10 (Cambridge, MA, Jan. 27–29, 2010), WSEAS Press, Athens, 2010, 415–420

[6] Brucker P., Knust S., Complexity results for scheduling problems, , Accessed Oct. 13, 2015 http://www.informatik.uni-osnabrueck.de/knust/class/