Previous Page | Next Page

The CLP Procedure

Edge Finding

Edge-finding (EF) techniques are effective propagation techniques for resource capacity constraints that reason about the processing order of a set of activities requiring a given resource or set of resources. Some of the typical ordering relationships that EF techniques can determine are whether an activity can, cannot, or must execute before (or after) a set of activities requiring the same resource or set of resources. This in turn determines new time bounds on the start and finish times. Carlier and Pinson (1989) were responsible for some of the earliest work in this area that resulted in solving MT10, a 10×10 job shop problem that had remained unsolved for over 20 years (Muth and Thompson; 1963). Since then, there have been several variations and extensions of this work (Carlier and Pinson; 1990; Applegate and Cook; 1991; Nuijten; 1994; Baptiste and Le Pape; 1996).

The edge-finding consistency routines are invoked by specifying the EDGEFINDER= or EDGE= option in the SCHEDULE statement. Specifying EDGEFINDER=FIRST computes an upper bound on the activity finish time by detecting whether a given activity must be processed first from a set of activities requiring the same resource or set of resources. Specifying EDGEFINDER=LAST computes a lower bound on the activity start time by detecting whether a given activity must be processed last from a set of activities requiring the same resource or set of resources. Specifying EDGEFINDER=BOTH is equivalent to specifying both EDGEFINDER=FIRST and EDGEFINDER=LAST.

An extension of the edge-finding consistency routines is in determining whether an activity cannot be the first to be processed or whether an activity cannot be the last to be processed from a given set of activities requiring the same resource (set of resources). The NOTFIRST= or NF= option in the SCHEDULE statement determines whether an activity is "not first." In similar fashion, the NOTLAST= or NL= option in the SCHEDULE statement determines whether an activity is "not last."


Note: This procedure is experimental.

Previous Page | Next Page | Top of Page