CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

authors Balas, Egon
year 1984
title On the Facial Structure of Scheduling Polyhedra
source 49 p., 6 p. of appendix : ill. Pittsburgh, PA: Design Research Center, Carnegie Mellon Univ., December, 1984. includes bibliography
summary A well-known 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 facets inducing inequalities for the scheduling polyhedron P(K) defined on some clique with node set K, and gives 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 HCK, 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 p-1 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
keywords polyhedra, graphs, optimization, convex hull
series CADline
references Content-type: text/plain
last changed 1999/02/12 14:07
HOMELOGIN (you are user _anon_754781 from group guest) Works Powered by SciX Open Publishing Services 1.002