《1996 A new approach to computing optimal schedules for the job-shop scheduling problem》.pdf

A New Approach to Computing Optimal Schedules for the Job-Shop Scheduling Problem Paul Martin * and David B. Shmoys ** School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY 14853. A b s t r a c t . From a computational point of view, the job-shop scheduling problem is one of the most notoriously intractable AlP-hard optimiza- tion problems. In spite of a great deal of substantive research, there are instances of even quite modest size for which it is beyond our cur- rent understanding to solve to optimality. We propose several new lower bounding procedures for this problem, and show how to incorporate them into a branch-and-bound procedure. Unlike almost all of the work done on this problem in the past thirty years, our enumerative procedure is not based on the disjunctive graph formulation, but is rather a time- oriented branching scheme. We show that our approach can solve most of the standard benchmark instances, and obtains the best known lower bounds on each. 1 Introduction In the job-shop scheduling problem we are given a set of n jobs, if, a set of m machines, .A4, and a set of operations, O. Each job consists of a chain of operations, let Oj be the chain of operations required by job j, whereas 0 i is the set of operations that must be processed on machine i. Each operation k requires a specified amount of processing I Pk, on a specified machine M(k). A schedule is an assignment of sta