
Accession Number : ADA136983
Title : On the Facial Structure of Scheduling Polyhedra.
Descriptive Note : Management sciences research rept.,
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Balas,E
PDF Url : ADA136983
Report Date : Aug 1983
Pagination or Media Count : 56
Abstract : A wellknown job shop scheduling problem can be formulated as follows. Given a graph G with node set N and with directed and undirected arcs, find an orientation of the undirected arcs that minimizes the length of a longest path in G. The author treats the problem as a disjunctive program, without recourse to integer variables, and give a partial characterization of the scheduling polyhedron P(N), i.e., the convex hull of feasible schedules. In particular, he derives all the facet inducing inequalities for the scheduling polyhedron P(K) defined on some clique with node set K, and give a sufficient condition for such inequalities to also induce facets of P(N). One of our results is that any inequality that induces a facet of P(H) for some H properly included in K, also induces a facet of P(K). Another one is a recursive formula for deriving a facet inducing inequality with p positive coefficients from one with p1 positive coefficients. The author also addresses the constraint identification problem, and gives a procedure for finding an inequality that cuts off a given solution to a subset of the constraints. (Author)
Descriptors : *Mathematical models, *Job shop scheduling, *Convex sets, Convex bodies, Inequalities, Coefficients, Graphs, Sequential analysis, Nodes, Combinatorial analysis
Subject Categories : Administration and Management
Statistics and Probability
Distribution Statement : APPROVED FOR PUBLIC RELEASE