Production scheduling and queueing: Deterministic and stochastic models

Scheduling and queueing models are useful aids for the design and analysis of manufacturing and service systems. Scheduling models are used to help finding operating rules that aim at the optimization of given objective functions. Queueing models are usually used when time averages and the steady state behavior of the systems under fixed operating rules (e.g., FIFO) are a major concern.;We first study proportionate flow shops; there jobs have to be processed by a number of machines in series and each job has the same processing requirements on all machines. Both stochastic and deterministic models are studied. Optimal schedules are found to minimize various cost functions of interest under different conditions. This model has applications in many practical situations. In telecommunication systems a message is transmitted through the network along a fixed route. The processing times of this message at all stations, which mainly depend on the length of this message, are approximately the same. In practice, scheduling problems with multiple objectives are seen frequently. A decision maker is often concerned not only with customer satisfaction but also with reducing production cost. Bicriteria scheduling in a single machine environment is studied along this line of research. Polynomial time algorithms are presented to find all Pareto optimal solutions for problems with mean flow time and maximum tardiness criteria. An open shop scheduling problem, which can also be interpreted as an optimal server allocation problem in a network of queues, is solved. The problem has new features like job arrivals and a transient cost function. A network of queues with batch services and assemblies is found to have a product form solution with novel type of traffic equations. Stability conditions of this network is also studied, these results together completely characterize the long run behavior of this network.;The development of real time scheduling systems is a current need and is likely to be even more important in the future. As a bridge between scheduling theory and such a need, computerized scheduling systems can provide user-friendly graphical interface which integrate theoretical algorithms and the scheduler's experience and intuition. Some issues relevant to the design and implementation of such scheduling systems are also explored.