Geodesic
Scheduling unit-time jobs on parallel processors polytope
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 1, pp. 85-97.

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

The polytope of scheduling unit-time jobs on identical parallel machines is studied. In addition, we consider LP relaxation and describe the class supporting inequalities for this polytope. We claim that obtained inequalities can be used as cutting planes for integer programming. We discuss the identification problem of these inequalities for the given nonintegral point. Il. 1, tabl. 1, bibliogr. 5.
Keywords: scheduling problems, precedence, integer programming, polytope, supporting inequality. 
@article{DA_2011_18_1_a8,
     author = {R. Yu. Simanchev and I. V. Urazova},
     title = {Scheduling unit-time jobs on parallel processors polytope},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {85--97},
     publisher = {mathdoc},
     volume = {18},
     number = {1},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_1_a8/}
}
TY  - JOUR
AU  - R. Yu. Simanchev
AU  - I. V. Urazova
TI  - Scheduling unit-time jobs on parallel processors polytope
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 85
EP  - 97
VL  - 18
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_1_a8/
LA  - ru
ID  - DA_2011_18_1_a8
ER  - 
%0 Journal Article
%A R. Yu. Simanchev
%A I. V. Urazova
%T Scheduling unit-time jobs on parallel processors polytope
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 85-97
%V 18
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2011_18_1_a8/
%G ru
%F DA_2011_18_1_a8
R. Yu. Simanchev; I. V. Urazova. Scheduling unit-time jobs on parallel processors polytope. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 1, pp. 85-97. http://geodesic.mathdoc.fr/item/DA_2011_18_1_a8/

[1] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[2] Kristofides N., Teoriya grafov. Algoritmicheskii podkhod, Mir, M., 1978, 431 pp. | MR

[3] Tanaev V. S., Gordon V. S., Shafranskii Ya. M., Teoriya raspisanii. Odnostadiinye sistemy, Nauka, M., 1984, 382 pp. | MR | Zbl

[4] Lawler E. L., Combinatorial optimization: networks and matroids, Holt, Rinehart, and Winston, New York, 1976, 374 pp. | MR | Zbl

[5] http://www.mathematik.uni-osnabrueck.de/knust/class