Constraint-directed techniques for scheduling alternative activities.

*(English)*Zbl 0948.68009Summary: We expand the scope of constraint-directed scheduling techniques to deal with the case where the scheduling problem includes alternative activities. That is, not only does the scheduling problem consist of determining when an activity is to execute, but also determining which set of alternative activities is to execute at all. Such problems encompass both alternative resource problems and alternative process plan problems. We formulate a constraint-based representation of alternative activities to model problems containing such choices. We then extend existing constraint-directed scheduling heuristic commitment techniques and propagators to reason directly about the fact that an activity does not necessarily have to exist in a final schedule. Experimental results show that an algorithm using a novel texture-based heuristic commitment technique together with extended edge-finding propagators achieves the best overall performance of the techniques tested.

##### MSC:

68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |

PDF
BibTeX
XML
Cite

\textit{J. C. Beck} and \textit{M. S. Fox}, Artif. Intell. 121, No. 1--2, 211--250 (2000; Zbl 0948.68009)

Full Text:
DOI

##### References:

[1] | Baptiste, P.; Le Pape, C., Disjunctive constraints for manufacturing scheduling: principles and extensions, () |

[2] | Baptiste, P.; Le Pape, C., Edge-finding constraint propagation algorithms for disjunctive and cumulative scheduling, (), Available from http://www.hds.utc.fr/ baptiste/ |

[3] | Baptiste, P.; Le Pape, C.; Nuijten, W., Incorporating efficient operations research algorithms in constraint-based scheduling, (), Workshop proceedings available on world wide web from http://www.cirl.uoregon.edu/aior/ |

[4] | Beck, J.C., Texture measurements as a basis for heuristic commitment techniques in constraint-directed scheduling, ph.D. thesis, (1999), University of Toronto |

[5] | Beck, J.C.; Davenport, A.J.; Davis, E.D.; Fox, M.S., The ODO project: toward a unified basis for constraint-directed scheduling, J. scheduling, Vol. 1, 2, 89-125, (1998) · Zbl 0909.90171 |

[6] | J.C. Beck, A.J. Davenport, C. Le Pape, Introduction to the special issue on industrial constraint-directed scheduling, CONSTRAINTS, in press · Zbl 0967.68503 |

[7] | Beck, J.C.; Davenport, A.J.; Sitarski, E.M.; Fox, M.S., Beyond contention: extending texture-based scheduling heuristics, () |

[8] | Beck, J.C.; Davenport, A.J.; Sitarski, E.M.; Fox, M.S., Texture-based heuristics for scheduling revisited, () |

[9] | Beck, J.C.; Jackson, K., Constrainedness and the phase transition in job shop scheduling, technical report, (1997), School of Computing Science, Simon Fraser University Burnaby, BC |

[10] | Beck, J.C.; Fox, M.S., Dynamic problem structure analysis as as basis for constraint-directed scheduling heuristics, Artificial intelligence, Vol. 117, 31-81, (2000) · Zbl 0939.68536 |

[11] | Brucker, P.; Thiele, O., A branch & bound method for the general-shop problems with sequence dependent set-up times, OR spektrum, Vol. 18, 145-161, (1996) · Zbl 0852.90087 |

[12] | Carlier, J.; Pinson, E., An algorithm for solving the job-shop problem, Management sci., Vol. 35, 2, 164-176, (1989) · Zbl 0677.90036 |

[13] | Carlier, J.; Pinson, E., Adjustment of heads and tails for the job-shop problem, European J. oper. res., Vol. 78, 146-161, (1994) · Zbl 0812.90063 |

[14] | Carnegie group inc., knowledge-based logistics planning system, internal documentation, (1994) |

[15] | Caseau, Y.; Laburthe, F., Improved CLP scheduling with task intervals, () |

[16] | Caseau, Y.; Laburthe, F., Improving branch and bound for jobshop scheduling with constraint propagation, () |

[17] | Cheng, C.C.; Smith, S.F., Applying constraint satisfaction techniques to job shop scheduling, Ann. oper. res. (special volume on scheduling: theory and practice), Vol. 70, 327-378, (1997) · Zbl 0890.90093 |

[18] | Cohen, P.R., Empirical methods for artificial intelligence, (1995), MIT Press Cambridge, MA · Zbl 0850.68260 |

[19] | Davenport, A.J.; Beck, J.C., An investigation into two approaches for resource allocation and scheduling, () |

[20] | Dubois, D.; Fargier, H.; Prade, H., The use of fuzzy constraints in job-shop scheduling, () · Zbl 1028.91526 |

[21] | Fox, M.S., Constraint-directed search: A case study of job-shop scheduling, ph.D. thesis, (1983), Carnegie Mellon University, Intelligent Systems Laboratory, The Robotics Institute Pittsburgh, PA, CMU-RI-TR-85-7 |

[22] | Fox, M.S.; Sadeh, N.; Baykan, C., Constrained heuristic search, (), 309-316 |

[23] | Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman New York · Zbl 0411.68039 |

[24] | Gent, I.P.; MacIntyre, E.; Prosser, P.; Walsh, T., The constrainedness of search, (), 246-252 |

[25] | Gent, I.P.; Walsh, T., The hardest random SAT problems, (), 355-366 |

[26] | Hildum, D.W., Flexibility in a knowledge-based system for solving dynamic resource-constrained scheduling problems, ph.D. thesis, (1994), Department of Computer Science, University of Massachusetts Amherst, MA, UMass CMPSCI TR 94-77 |

[27] | Kott, A.; Saks, V., A multi-decompositional approach to integration of planning and schedulingâ€”an applied perspective, () |

[28] | Le Pape, C., Using a constraint-based scheduling library to solve a specific scheduling problem, () |

[29] | Lhomme, O., Consistency techniques for numeric csps, (), 232-238 |

[30] | Mittal, S.; Falkenhainer, B., Dynamic constraint satisfaction problems, (), 25-32 |

[31] | Nuijten, W.P.M., Time and resource constrained scheduling: A constraint satisfaction approach, ph.D. thesis, (1994), Department of Mathematics and Computing Science, Eindhoven University of Technology · Zbl 0837.90068 |

[32] | Nuijten, W.P.M.; Aarts, E.H.L.; van Arp Taalman Kip, D.A.A.; van Hee, K.M., Randomized constraint satisfaction for job shop scheduling, (), 251-262 |

[33] | Roberts, F.S., Applied combinatorics, (1984), Prentice Hall Englewood Cliffs, NJ · Zbl 0547.05001 |

[34] | Ruttkay, Z., Fuzzy constraint satisfaction, (), 1263-1268 |

[35] | Sabin, M.; Freuder, E.C., Detecting and resolving inconsistency and redundancy in conditional constraint satisfaction problems, () |

[36] | Sadeh, N., Lookahead techniques for micro-opportunistic job-shop scheduling, ph.D. thesis, (1991), Carnegie-Mellon University Pittsburgh, PA, CMU-CS-91-102 |

[37] | Sadeh, N.; Fox, M.S., Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem, Artificial intelligence, Vol. 86, 1, 1-41, (1996) |

[38] | Sadeh, N.M.; Hildum, D.W.; Laliberty, T.J.; McA’Nulty, J.; Kjenstad, D.; Tseng, A., A blackboard architecture for integrating process planning and production scheduling, Concurrent engineering: research and applications, Vol. 6, 2, (1998) |

[39] | Saks, V., Distribution planner overview, technical report, (1992), Carnegie Group, Inc Pittsburgh, PA |

[40] | Schiex, T.; Fargier, H.; Verfaillie, G., Valued constraint satisfaction problems: hard and easy problems, () |

[41] | Simon, H.A., The structure of ill-structured problems, Artificial intelligence, Vol. 4, 181-200, (1973) |

[42] | Smith, S.F.; Cheng, C.C., Slack-based heuristics for constraint satisfaction scheduling, (), 139-144 |

[43] | Wagner, T.; Garvey, A.; Lesser, V., Design-to-criteria scheduling: managing complexity through goal-directed satisficing, () |

[44] | Wagner, T.; Garvey, A.; Lesser, V., Criteria directed task scheduling, Internat. J. approx. reason., Vol. 19, 91-118, (1998) · Zbl 1044.90514 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.