Essays on machine scheduling problems

In the first chapter of this thesis we study the one machine scheduling problem, with release and delivery times, and the minimum makespan objective, in the presence of delayed precedence constraints. This problem arises naturally in the context of the Shifting Bottleneck Procedure for the general job shop scheduling problem as a relaxation of the latter, but tighter than the standard one machine relaxation. First, we highlight the difference between the two relaxations through some relevant complexity results. Then we introduce a modified Longest Tail Heuristic, whose analysis identifies those situations that permit efficient branching. An optimization algorithm is developed whose performance is comparable to that of the best algorithms for the standard one machine problem. Embedding this algorithm into a modified version of the Shifting Bottleneck Procedure results in a considerable overall improvement in performance.; The next topic is the development of a guided local search procedure for the job shop scheduling problem. We define a neighborhood structure which enables us to move an operation right before or right after another operation, with the conditions that both operations are on a critical path, and the resulting schedule is feasible. Next, we introduce the notion of a neighborhood tree. The nodes of this tree are schedules which can be obtained from the root node of the tree by performing a number of interchanges derived from the neighborhood structure. The size of a neighborhood tree is limited by a bounding function, and the search is directed by the neighborhood structure of the problem. Using the neighborhood tree, we develop a local search procedure (GLS) and embed this procedure into the Shifting Bottleneck Procedure. This new version of the SB Procedure produces schedules of high quality which approach optimality. We also introduce a randomization technique to generate new starting points and run the procedure. We present computational results using the new procedure and compare them with simulated annealing, three tabu search procedures, and a procedure based on genetic algorithms.; In Chapter 4, we develop a Shifting Bottleneck Procedure for job shop scheduling with deadlines. We formulate the one machine scheduling problem with deadlines and delayed precedence constraints, which arises as a relaxation of the job shop scheduling problem with deadlines. We develop an optimization method for this problem and use it to sequence the bottleneck machine. The deadlines are hard constraints and they have to be satisfied by the schedule obtained from the optimal one machine selection. But a feasible solution is not guaranteed; for certain configurations of the deadlines, we may not meet the scheduling criteria. Therefore, if the schedule produced (when the optimal sequence of the one machine problem is added) is not feasible, then we develop a perturbation method that heuristically attempts to transform it into a feasible schedule by making changes along the selections of sequenced machines.; In the last chapter, we describe a class of one machine scheduling problems which require an exponential number of nodes to prove optimality when using the current best optimization algorithm (Carlier's branch and bound method). We develop a new approximation procedure for the one machine scheduling problem called the Absolute Longest Tail Heuristic and analyze its properties. Using these properties, we develop a new optimization algorithm for the one machine scheduling problem and present our computational results. (Abstract shortened by UMI.)...