Probabilistic analysis and practical algorithms for machine scheduling problems with or without release date constraints

The area of scheduling has attracted significant research in the last four decades due to its applicability to a variety of commercial applications. Unfortunately, many scheduling problems are NP-hard which indicates that it is highly unlikely that these problems will be solved to optimality by a polynomial time algorithm.; Among the handful of the scheduling problems that are polynomially solvable, an important one is the Single Machine Weighted Completion Time problem. It is well known that this problem can be solved using the Weighted Shortest Processing Time rule.; Our objective in this dissertation is to illustrate how this simple dispatch rule can be modified for more complex scheduling problems. Specifically, we consider three seminal, NP-hard, scheduling problems and use probabilistic and asymptotic analysis to prove that variations of the Weighted Shortest Processing Time rule generates effective solutions.; The first problem studied in this dissertation is the Deterministic Flow Shop Weighted Completion Time Problem with Release Dates. For this problem, we focus on the analysis of the performance of several heuristics, all of which are related to the classical Weighted Shortest Processing Time among Available Jobs heuristic. By using probabilistic analysis, we prove that these heuristic are asymptotically optimal.; We next study the Deterministic Job Shop Weighted Completion Time Problem. To solve this problem, we develop a cyclic heuristic that schedules a certain number of jobs from a given type, i.e. jobs having the same routing, using a variant of the Weighted Shortest Processing Time heuristic. The heuristic then rotates from type to type in a cyclic order until all jobs are processed. Again, by using probabilistic analysis, we show that this heuristic generates a schedule with an arbitrarily small asymptotic relative error.; The last problem studied in this dissertation is the Stochastic Flow Shop Weighted Completion Time Problem with Release Dates. For this problem, we analyze the performance of the Weighted Shortest Expected Processing Time among Available Jobs heuristic. We prove that this heuristic is asymptotically optimal for this stochastic scheduling problem.