Volume 16, No 1, 2009, P. 3-36
UDC 519.854.2
P. Baptiste, J. Carlier, A. V. Kononov, M. Queyranne, S. V. Sevastjanov, M. I. Sviridenko
Structural properties of optimal schedules with preemption
Abstract:
Scheduling problems with preemption are considered, where each operation can be interrupted and resumed later without any penalty. We investigate some basic properties of their optimal solutions, such as the existence of an optimal schedule (provided that the set of feasible solutions is nonempty), the existence of such a solution with a finite/polynomial number of interruptions or with interruptions at integral points only. Such theoretical questions are also of practical interest, since structural properties can be used to reduce the search space in a practical scheduling application. In this paper we provide answers to these basic questions for a rather general scheduling model (including, as its special cases, such classical models as parallel machine scheduling, shop scheduling, and resource constrained project scheduling) and for a large variety of objective functions, including nearly all known. For two special cases of objective functions (including, however, all classical functions) we prove the existence of an optimal solution with a special “rational structure”. An important consequence of this property is that the decision versions of these optimization scheduling problems belong to class NP.
Tabl. 4, bibl. 12.
Keywords: scheduling theory, preemption, optimal schedule.
Baptiste Philipp 3
Carlier Jeanne 3
Kononov Alexandr Veniaminovich 1
Queyranne Maurice 4
Queyranne Maurice 1,2
Sviridenko Maxim 5
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2.
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
3. CNRS, Heudiasyc, Univ. de Tech. de Compiègne & École Polytechnique
4. Faculty of Commerce and Business Administration, University of British Columbia,
Vancouver, B.C., Canada V6T 1Z2
5. IBM T. J. Watson Research Center,
Yorktown Heights, USA
e-mail: baptiste@utc.fr, carlier@utc.fr, alvenko@math.nsc.ru, Maurice.Queyranne@commerce.ubc.ca, seva@math.nsc.ru, sviri@us.ibm.com
