next up previous
Next: References

Scheduling



The objective of the investigations is to study classes of scheduling problems arising in connection with production planning and with the design of computer operationg systems. Such problems are more complex than classical scheduling environments because in most cases several additional constraints have to be satisfied. We formulate models representing these problems and investigate basic solution methods. The main individual projects can be classified as follows:



Investigation of scheduling models and the structure of the set of feasible solutions of scheduling problems

Authors: Frank Werner
Cooperations: Heidemarie Bräsel (IAG of the Otto-von-Guericke-University Magdeburg); Natalia V. Shakhlevich (Institute of Engineering Cybernetics of Minsk); Yuri N. Sotskov (Institute of Engineering Cybernetics of Minsk); Vjacheslav S. Tanaev (Institute of Engineering Cybernetics of Minsk).
Support: Deutsche Forschungsgemeinschaft (project ScheMA), INTAS.


A popular model in scheduling theory is the disjunctive graph model. The network model based on such a disjunctive or mixed graph or on a multigraph allows the possibility of representing different constraints which often arise in production planning and scheduling. With such a model, parallel machines in multi-stage shop systems and some other features of real production systems can be taken into account. The discussion of the mixed multigraph model and some applications can be found for instance in [19].

Recently, the investigation of coloring problems on mixed graphs has begun. First results can be found in [27]. In the latter paper, also the chromatic polynomial of a mixed graph has been considered. Such investigations are of interest in connection with the determination of feasible schedules. Another topic are investigations of the set of feasible schedules for some types of scheduling problems in order to determine subsets of feasible schedules with certain properties. These investigations are in close connection to scheduling problems with uncertain numerical data.



Complexity investigations and development of polynomial algorithms for subclasses of scheduling problems

Authors: Volker Lauff, Frank Werner
Cooperations: Jacek Blazewicz (TU Poznan); Peter Brucker (Universität Osnabrück); Valery S. Gordon (Institue of Engineering Cybernetics of Minsk); Svetlana A. Kravchenko (Institute of Engineering of Minsk); Natalia V. Shakhlevich (Institute of Engineering Cybernetics of Minsk); Yuri N. Sotskov (Institute of Engineering Cybernetics of Minsk).
Support: Deutsche Forschungsgemeinschaft (project ScheMA), INTAS.


One aim is to classify scheduling problems according to their complexity. Only for special problems, polynomial algorithms have been developed. For NP-hard problems, dynamic programming algorithms, polynomial approximation schemes, branch and bound methods, decomposition approaches and heuristcs have been applied.

Our investigations include problems shop scheduling problems with a fixed number of jobs, with operations of equal duration and with setup times as well as single machine and parallel machine problems.

Mixed shop scheduling problems have been considered in [23] and [24]. Parallel machine problems with a singler server, which has to perform the loading of a job, have been investigated in [16] and [17]. The latter problems arise in connection with flexible manufacturing problems. Polynomially solvable cases of single machine problems with release dates, due dates and deadlines have been derived in [10] and [11]. Batch scheduling problems on parallel machines with deadlines have been investigated in [8].



Development of heuristic and approximative algorithms

Authors: Volker Lauff, Frank Werner
Cooperations: Jatinder N.D. Gupta (Ball State University Muncie); Mikhail Y. Kovalyov (Institute of Engineering Cybernetics of Minsk); Natalia V. Shakhlevich (Institute of Engineering Cybernetics of Minsk); Yuri N. Sotskov (Institute of Engineering Cybernetics of Minsk); Thomas Tautenhahn (IAG of the Otto-von-Guericke-University of Magdeburg).
Support: Deutsche Forschungsgemeinschaft (project ScheMA), INTAS.


A consequence of the complex nature of many scheduling problems is that the only practical approach is to apply approximative and heuristic methods. This includes constructive as well as iterative algorithms. Various local search heuristics including simulated annealing, tabu search and multi-level procedures are studied. Among the constructive algorithms, we investigate insertion-based algorithms as well as approximation schemes.

Among the problem types to be considered, we deal with generalized shop scheduling problems, scheduling problems with hierarchical optimization criteria, problems with nonregular criteria such as the minimization of the total earliness and tardiness penalties or scheduling problems combined with batching.

Heuristic algorithms for flow shop problems with batch processing have been given in [28], [29] and [9]. Algorithms for generalized shop scheduling problems can be found in [12] and [19]. A constructive algorithm for flow shop problems with hierarchical criteria is given in [13]. An approximation scheme for a 2-machine flow shop problem with release dates is given in [14]. An adaptive algorithm for a shop scheduling problem with makespan minimization has been given in [22].



Investigation of the stability of exact and approximative solutions

Authors: Nadejda Sotskova, Frank Werner
Cooperations: Tsung-Chyan Lai (University of Taipei); Yuri N. Sotskov (Insitute of Engineering Cybernetics of Minsk).
Support: Deutsche Forschungsgemeinschaft (project ScheMA), INTAS.


The usual assumption that the processing times of the operations are known in advance is the strictest one in deterministic scheduling theory and it essentially restricts its practical aspects. A stability analysis may help to extend the significance of scheduling theory for some production scheduling problems. The stability radius of an optimal schedule denoted the largest quantity of independent variations of the processing times of the operations such that this schedule remains optimal.

The calculation of the stability radius of an optimal or an approximate schedule for shop scheduling problems has been considered in [30]. The influence of errors and possible changes on the property of a schedule to be optimal for job shop problems has been investigated in [25].

Formulas for the calculation of the stabilitiy radius, when the objective is to minimize mean flow time for a general shop problem are given in [5]. A review on stability analysis has been given in [26].

Recently we started the investigation of shop scheduling problems with uncertain numerical input data, where only lower and upper bound for the processing times are known. Some first results for such problems are presented in [20] and [21].



 
next up previous
Next: References
Hugo
2/11/1999