On-line scheduling and dynamic task assignment

Some of the important decision problems in production systems, information processing, or telecommunication systems are those of scheduling and dynamic allocation of resources. Studies of scheduling problems have been done by researchers from many different areas for the last 40 years. Much of this work is concerned with static problems, i.e., problems where all of the information about the system is known a priori. Developments in technologies in the different application areas raised the need of solving complex scheduling and task assignment problems dynamically. Furthermore, many of the real world systems have to deal with incomplete information. Hence the problem of scheduling in dynamic environments takes an important position. In this thesis we investigate several new paradigms for dealing with scheduling in dynamic environments. A natural approach to consider is that of maintaining a rolling schedule that is optimal with respect to the information that is currently available. This raises two issues. One is to design computational methods for efficient dynamic reoptimization and the other issue is to evaluate the soundness of the rolling schedule. We call these issues the efficiency and competitiveness of on-line schedules and illustrate their resolution in the case of n $\vert$ 1 $\vert$ prec $\vert$ $f\sb{max}$ scheduling problem. Another issue we have studied in this thesis is of on-line task assignment in multiprocessor systems in which the true status of processors availability may be obtained by querying at cost. Some results on optimal policies for querying and assignment are presented under the assumption of independent completion times for the processors. In situations where the assumption of independent completion times is difficult to justify, we present a general recursive scheme based on Bayesian updating for optimal querying policies. Finally, we also study the problem of single server stochastic scheduling to minimize the expected system time of jobs with switch-over (set-up) costs. We analyze an exhaustive cyclic policy to control a symmetric system. For system with low arrival rates, we propose a median policy, and prove the optimality of this policy