On-line scheduling with constraints

© 2009 Dr. Lele ZhangScheduling is concerned with the process of deciding how to commit resources between a variety of possible tasks with the aim of optimizing some performance criterion. Efficient scheduling is a vital tool in successful decision-making. To date, an enormous amount of research has been done on scheduling problems arising from various disciplines. Major attention has so far been dedicated to off-line (usually deterministic) scheduling problems. Off-line deterministic scheduling deals with perfect information. That is, all information with regard to a problem is known prior to any decision. However, this perfect information assumption violates the nature of many realistic issues with uncertainties, for example, a situation where the knowledge of problem instances is revealed over time, or a scenario in which processing tasks are temporarily disrupted or cancelled. To better formulate this sort of problem with high uncertainties, a new concept of on-line scheduling was introduced. On-line approaches have become increasingly important and are frequently encountered when only partial knowledge is available but instant or very fast solution methods are required and should nevertheless result in good outcomes. In on-line scheduling, a decision maker allocates resources between tasks as the information is gradually released. Obviously, given the same scheduling environment and problem instance, the result produced by an on-line scheduler cannot be better than that by the optimal off-line scheduler; but the on-line scheduling technique immunizes schedules from future disruptions and uncertainties. This thesis extends the study of some scheduling problems derived from various industrial and computing situations to on-line scheduling environments, specifically the on-line-list and the on-line-time paradigms. The six topics studied are classified in two parts in this thesis. Part I consists of three machine scheduling problems taking into account various types of setup considerations. Part II includes the other three scheduling problems which are closely related to issues arising in the management of shipping containers and wind energy. The effort is focused on constructing effective and efficient (on-line) decision-making strategies with the purpose of optimizing certain objective measures in those uncertain scheduling environments. The performance of the proposed heuristics as well as some existing on-line algorithms is evaluated and compared via competitive analysis. For some cases, empirical studies are also carried out to assess their average performance