Asymptotic performance analyses of machine scheduling problems with release dates

Scheduling problems are important in a wide range of commercial applications, but unfortunately, these problems are quite difficult to solve.; For a variety of scheduling problems we identify asymptotically optimal on-line algorithms.; We first consider the single machine weighted completion time problem with release dates. In this problem, we are given a set of jobs which have to be processed non-preemptively on a single machine. We analyze the performance of the Weighted Shortest Processing Time among Available jobs (WSPTA) algorithm. We prove that this simple on-line algorithm is asymptotically optimal.; We then consider a more general model, the uniform parallel machine weighted completion time problem with release dates which can be described as follows. Jobs arriving over time must be non-preemptively processed on one of m parallel machines, each of which running at its own speed. No job can be processed before its release date, and the objective is to assign jobs to the machines and find a processing order so as to minimize the sum of the weighted completion times of all jobs.; Using the notion of mean busy dates, we extend the results developed for the single machine problem to the uniform parallel machine model. Specifically, we consider the Weighted Shortest Processing Requirement (WSPR) algorithm, which is a direct extension of the WSPTA algorithm. We prove that this on-line algorithm is asymptotically optimal. Our proof relies extensively on properties of optimal solutions to a single machine relaxation of the problem and does not require any probabilistic assumption on the job parameters.; We also consider a stochastic version of the single machine model. This problem is very similar to the first problem considered except that the actual processing times are not known until processing is completed. For this problem we analyze the performance of the Weighted Shortest Expected Processing Time among Available jobs (WSEPTA) algorithm, which is an on-line nonpreemptive heuristic. We prove that under some assumptions on the job parameters, this on-line WSEPTA algorithm is asymptotically optimal.; Finally, we consider the open shop problem without release dates. We present a relaxation of this problem and characterize properties of the optimal solution of the relaxation. We show that this relaxation provides an asymptotically tight lower bound. (Abstract shortened by UMI.)...