No description available.

No description available.

The problem of scheduling tasks onto multiprocessor systems has increasing practical importance as more applications are being addressed with multiprocessor systems. Actual applications and multiprocessor systems have many characteristics which become constraints to the general scheduling problem of minimizing the schedule length. These practical constraints include precedence relations and communication delays between tasks, yet few researchers have considered both these constraints when developing schedulers. This work examines a more general multiprocessor scheduling problem, which includes these practical scheduling constraints, and develops a new scheduling heuristic using a list scheduler with dynamically computed priorities. The dynamic priority heuristic is compared against an optimal scheduler and against other researchers’ approaches for thousands of randomly generated scheduling problems. The dynamic priority heuristic produces schedules with lengths which are 10% to 20% over optimal on the average. The dynamic priority heuristic performs better than other researchers’ approaches for scheduling problems with the practical constraints. We conclude that it is important to consider practical constraints in the design of a scheduler and that a simple heuristic can still achieve good performance in this area.

No description available.

This thesis addresses an airline crew allocation and scheduling problem faced by certain divisions of the United States Air Force. Three variants of the problem under consideration were posed by the Brooks U.S. Air Force Base. This thesis reports on experience with two heuristic methods developed, each applicable to the different variants of the problem. Although the problem described herein is peculiar to this situation, the heuristic scheduling and dispatching rules developed have been found to be very effective, and are generally applicable in other related contexts of routing, and crew and vehicle scheduling problems as well. The two algorithms developed have been applied to a coded set of real world data. The results indicate that each one of the two methods is preferable over the other for one of the two variants of the problem, and they are equally effective for the third variant. The observations made in this study suggest an overall effective composite technique for this class of problems. / Master of Science

This research investigated applying Artificial Intelligence (AI) method to develop a scheduling and sequencing system for parallel processors, subject to preference, sequencing, and buffer inventory constraints. Specifically, hierarchical planning and, constraint-directed search were used to develop prototype scheduling system for a case study problem. This research also investigated dividing the scheduling problem into sub-periods to allow parallel scheduling and efficient handling of time-dependent, constraints. The prototype system uses, problem-constraints to define sub-period boundaries, and determine which processors and jobs to include in the sub-period problems. It then solves the sub-period schedules in sequence. The prototype system was tested using operational data from the case study and compared to schedules created by the case study scheduler. The prototype system produced schedules very similar to the human scheduler, and relaxed constraints only slightly more than the scheduler in searching for solutions. The success of the prototype system demonstrated: 1) the effectiveness of hierarchical planning and constraint-directed search as methods for developing scheduling systems for parallel processors; 2) that constraint satisfaction, as opposed to solving an objective function, is a useful alternative method for modeling scheduling problems; and 3) dividing the scheduling problem into sub-period problems reduces the size of the search space- encountered in parallel scheduling while allowing fulfillment of time dependent constraints. / Master of Science

A comparative simulation study was performed to investigate the effect of uncertainty or unreliability in job processing times on designing schedules in a pure job shop environment. Five performance measures were employed in an effort to examine the effect of variations between estimated and actual processing times. These variations are common in job shop systems where estimations are used to set processing times. It was hypothesized that a variation has an effect on relative system performance. In addition, three priority rules, namely, FIFO, SOT and EDD, were studied to determine the best rule for controlling the shop in situations of unreliable processing times data. The percentage variation in processing times was clearly the dominant variable for most of the performance measures. A 60% variation in estimated processing times appeared to be the maximum level under which the mean flowtime, mean tardiness and percent of late jobs performance measures were insensitive. The simulation results indicated that the makespan and average shop utilization performance measures were insensitive to reliability of input information about processing times for up to a 100%. The performance of FIFO and EDD priority rules suffered drastically while SOT was the least sensitive to the reliability of processing times information. / M.S.

A model is developed to describe the total expected cost per unit time of monitoring the mean of a production process with a Variable Sampling Interval control chart. This chart has the feature that the time delay between successive samples is not constant but depends on the result of the most recent sample observation. The model assumes that the quality characteristic of interest is distributed normally with known, constant variance. Process states are defined to derive a Markov chain model. The solution to its steady state probability equations is obtained in terms of decision variables pertinent to the economic design of control charts. Each entry in the resulting probability vector is interpreted as the average proportion of time spent in the corresponding process state. The cost of occupying each state is also defined in terms of the model parameters, and the total expected cost is given as the product of the cost and probability vectors. This product is then divided by the product of the probability vector and the vector comprising the time durations of each state to obtain a total expected cost per unit time model. Model behavior is analyzed to determine that Variable Sampling Interval control charts for means are economically attractive when sampling/inspection costs and nonconforming product costs as defined in this paper are of similar magnitude. Variable Sampling Interval charts are not attractive economically when either of those cost categories dominates the other. / M.S.

No description available.

In this dissertation we present new results for minimizing the makespan in a flow shop with zero storage between machines. Makespan is the total length of time required to process a set of jobs. We consider m machines and n jobs with random processing times. Since there is no intermediate storage between machines, a job that has finished processing at one machine may have to stay on that machine until the next machine is free. Our goal is to select a schedule that will minimize the makespan. Our results require various stochastic orderings of the processing time distributions. Some orderings minimize the expected makespan, and some stronger results stochastically minimize the makespan. The optimum sequence of these latter cases not only minimizes the expected makespan but also maximizes the probability of completing a set of jobs by time t for any t. The last result is concerned with scheduling jobs on two identical parallel machines. The jobs are subjected to some intree precedence constraints. We resolve a conjecture that appeared in Pinedo and Weiss (1985) and give conditions under which the conjecture is true and give examples to prove that the conjecture is false in general. / Ph. D.