Arrow Research search

Author name cluster

Mark S. Fox

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers
2 author rows

Possible papers

11

AIJ Journal 2000 Journal Article

Constraint-directed techniques for scheduling alternative activities

  • J.Christopher Beck
  • Mark S. Fox

In this paper, 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.

Details DOI

AIJ Journal 2000 Journal Article

Dynamic problem structure analysis as a basis for constraint-directed scheduling heuristics

  • J.Christopher Beck
  • Mark S. Fox

While the exploitation of problem structure by heuristic search techniques has a long history in AI (Simon, 1973), many of the advances in constraint-directed scheduling technology in the 1990s have resulted from the creation of powerful propagation techniques. In this paper, we return to the hypothesis that understanding of problem structure plays a critical role in successful heuristic search even in the presence of powerful propagators. In particular, we examine three heuristic commitment techniques and show that the two techniques based on dynamic problem structure analysis achieve superior performance across all experiments. More interestingly, we demonstrate that the heuristic commitment technique that exploits dynamic resource-level non-uniformities achieves superior overall performance when those non-uniformities are present in the problem instances.

Details DOI

AAAI Conference 1999 Conference Paper

Scheduling Alternative Activities

  • J. Christopher Beck
  • ILOG
  • S.A.
  • Mark S. Fox
  • University of Toronto

In realistic scheduling problems, there may be choices among resources or among process plans. We formulate a constraint-based representation of alternative activities to model problems containing such choices. We 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.

PDF Details

AIJ Journal 1996 Journal Article

Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem

  • Norman Sadeh
  • Mark S. Fox

Practical constraint satisfaction problems (CSPs) such as design of integrated circuits or scheduling generally entail large search spaces with hundreds or even thousands of variables, each with hundreds or thousands of possible values. Often, only a very tiny fraction of all these possible assignments participates in a satisfactory solution. This article discusses techniques that aim at reducing the effective size of the search space to be explored in order to find a satisfactory solution by judiciously selecting the order in which variables are instantiated and the sequence in which possible values are tried for each variable. In the CSP literature, these techniques are commonly referred to as variable and value ordering heuristics. Our investigation is conducted in the job shop scheduling domain. We show that, in contrast with problems studied earlier in the CSP literature, generic variable and value heuristics do not perform well in this domain. This is attributed to the difficulty of these heuristics to properly account for the tightness of constraints and/or the connectivity of the constraint graphs induced by job shop scheduling CSPs. A new probabilistic framework is introduced that better captures these key aspects of the job shop scheduling search space. Empirical results show that variable and value ordering heuristics derived within this probabilistic framework often yield significant improvements in search efficiency and significant reductions in the search time required to obtain a satisfactory solution. The research reported in this article was the first one, along with the work of Keng and Yun (1989), to use the CSP problem solving paradigm to solve job shop scheduling problems. The suite of benchmark problems it introduced has been used since then by a number of other researchers to evaluate alternative techniques for the job shop scheduling CSP. The article briefly reviews some of these more recent efforts and shows that our variable and value ordering heuristics remain quite competitive

Details DOI

IJCAI Conference 1983 Conference Paper

Techniques for Sensor-Based Diagnosis

  • Mark S. Fox
  • Simon Lowenfeld
  • Pamela Kleinosky

This paper describes a system called PDS, a forward chaining, rule-based architecture designed for the online, realtime diagnosis of machine processes. Two issues arise in the application of expert systems to the analysis of sensor-based data: spurious readings and sensor degradation. PDS implements techniques called retrospective analysis and meta-diagnosis as solutions to these problems. These techniques and our experiences in knowledge acquisition in a large organization, and the implementation of PDS as a portable diagnostic tool are described.

PDF

AAAI Conference 1982 Conference Paper

Job-Shop Scheduling: An Investigation in Constraint-Directed Reasoning

  • Mark S. Fox

This paper describes ISIS-II*, a constraint-directed reasoning system for the scheduling of factory job-shops. ISIS-II takes a heuristic search approach to generating schedules. The key features of ISIS-II’s approach is that it can re- present and use a variety of different types of constraints to guide the search, and is able to selectively relax conflicting constraints.

PDF Details