Contributions to the job shop scheduling problem

In this thesis we study several approaches to job-shop scheduling problems. Chapter 1 introduces the basic definitions, notations and concepts used in scheduling theory. Then we present a short summary of the major results in deterministic scheduling theory. Four different approaches to solving job-shop scheduling problems are discussed. Finally, a short review of complexity theory is given along with a summary of the known complexity results for job-shop scheduling problems.; Traditional mathematical programming techniques are not capable of solving job-shop scheduling problems of practical sizes. Consequently, we consider a polyhedral approach that has been shown elsewhere to be successful in the resolution of large-scale zero-one and mixed-zero-one linear programming problems. The mathematical concepts that are needed are presented in Chapter 2.; In Chapter 3, mathematical formulations for job-shop scheduling problems are presented. A traditional mathematical formulation for a job-shop scheduling problem by Manne (1960) is introduced first. To overcome the nonconvexity of the feasible set in Manne's formulation, we follow the usual method and introduce zero-one variables and upper bounds into the formulation. We explore the convex hull of the feasible set to get a linear description for our model and obtain an improved formulation for the problem. We also compare our approach to the disjunctive programming approach and obtain a generalization of a result by Queyranne (1988) regarding the complete linear description of a 1-machine problem.; 1-machine job-shop scheduling problems are discussed in Chapter 4. The results of this chapter can be used as basic blocks for more general cases. We begin with a complete mathematical description for a 1-machine scheduling problem. We obtain a complete linear description of the general completion time model modulo the ordering polytope which yields a slight generalization of Smith's rule. A partial linear description and certain classes of facets of the basic lateness model are derived. Through the use of the (S,T)-inequalities we prove Jackson's rule and the slack-time rule by way of linear programming. For the general tardiness model we describe 2n{dollar}sp2{dollar} new facets and generalize some of them to a substantially larger class. Our results for this problem can be used in a branch-and-cut method to solve the general tardiness problems.