The CLP Procedure
-
Overview
-
Getting Started
-
Syntax
-
Details
-
ExamplesLogic-Based PuzzlesAlphabet Blocks ProblemWork-Shift Scheduling ProblemA Nonlinear Optimization ProblemCar Painting ProblemScene Allocation ProblemCar Sequencing ProblemRound-Robin ProblemResource-Constrained Scheduling with Nonstandard Temporal ConstraintsScheduling with Alternate Resources10×10 Job Shop Scheduling ProblemScheduling a Major Basketball ConferenceBalanced Incomplete Block DesignProgressive Party ProblemStatement and Option Cross-Reference Table
- References
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 that require 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 that require the same resource or set of resources. This in turn determines new time bounds on the start and finish times. Carlier and Pinson (1989) are responsible for some of the earliest work in this area, which 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).
You invoke the edge-finding consistency routines 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 that require 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 that require 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 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 that require the same resource or set of resources. The NOTFIRST= or NF= option in the SCHEDULE statement determines whether an activity must not be the first to be processed. In similar fashion, the NOTLAST= or NL= option in the SCHEDULE statement determines whether an activity must not be the last to be processed.