Probabilistic analysis and effective algorithms for large-scale machine scheduling problems

In manufacturing facilities, achieving efficient utilization of resources and a high level of customer service are typically conflicting goals. Customer service goals such as on time delivery can easily be met if there is excess capacity which increases the flexibility of manufacturing operations, but excess capacity implies that available resources are not completely utilized. Production Scheduling Techniques, which involve the allocation of limited resources over tasks in order to meet some objective or set of objectives, are one way to address this conflict.; In this thesis, we focus on two particular production scheduling models, a flow-shop model and a single machine model with release dates, which contain elements of large scale scheduling problems we have seen in practice. Specifically, we are motivated by the success we had using the Weighted Shortest Processing Time (WSPT) algorithm--in which jobs are sequenced in decreasing order of their ratio of weights to processing times--to develop effective solutions to some large-scale, industrial scheduling problems.; Unlike most previous work, we utilize the tools of probabilistic analysis in order to demonstrate that the asymptotic optimal objective value of the flowshop problem is directly related to the asymptotic objective value of certain single and parallel machine models. Since some of these models are solved optimally using the SPT heuristic, we next determine conditions under which SPT is asymptotically optimal for this flowshop model.; Computational tests of the SPT rule for various randomly generated test problems indicate that although this rule is effective for large numbers of jobs and small numbers of machines, it is less effective for more machines or fewer jobs.; Thus, using the insight developed from the analysis, we develop a heuristic which improves this performance. Computational experiments show that the new heuristic significantly outperforms the WSPT rule on a large set of test problems.; Finally, we apply probabilistic analysis to the single machine problem with release dates. Although problems with release dates are much more complex, we show that the Shortest Processing Time Among Available Jobs heuristic is asymptotically optimal. This is particularly appealing because this heuristic is a computationally efficient on-line algorithm.