Volume 18, No 1, 2011, P. 85-97

UDC 519.6
R. Yu. Simanchev, I. V. Urazova
Scheduling unit-time jobs on parallel processors polytope

Abstract:
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.

Simanchev Ruslan Yur’evich ¹
Urazova Inna Vladimirovna ¹
1. Omsk State University,
55a Mira ave., 644077 Omsk, Russia
e-mail: osiman@rambler.ru, urazovainn@mail.ru