Intelligent Workflow - State of the Art Scheduling - A Difficult Problem

Why is Scheduling so Difficult?

There are three characteristics which cause scheduling to be extremely difficult to automate and existing techniques unsatisfactory:
  1. its combinatorial complexity (scheduling is an NP hard problem)
  2. the conflicting nature of the requirements of a "good" schedule
  3. the uncertainty of execution caused by the stochastic and dynamic nature of most scheduling environments

Complexity

The most prominent feature of scheduling problems is their combinatorial explosiven ess. The general job-shop scheduling problem with n jobs, and m machines has an infinite number of feasible solutions since idle times between operations can vary. Most scheduling domains have similar or greater complexity. (Conway et al. '67) Simply put, the number of feasible schedules grows exponentially along each dimension (machines, tools, orders, etc). Most combinatorial optimisation problems are in the NP class, (Gonzalez & Sahni '78 ), and are therefore difficult to solve since only inefficient non-deterministic* polynomial algorithms are available. All scheduling problems, except a few very simplistic ones, belong to this NP class. A subset of NP problems was identified, (Cook '71), and termed NP complete. These are problems which can be transformed by a property called reducibilityto the satisfiability problem, (Karp '72; Karp '75) Again scheduling generally fits into this class of problem which has, as yet, no satisfactory solution.

Conflicting Objectives

A second difficulty with scheduling involves assessing the value of a scheduling decision within a specific domain. Often it is unclear how one decision will influence the global satisfaction of organisational goals such as machine utilisation, due dates or work in progress (WIP) levels. An example of this difficulty is given by (Rickel, '88).
"Suppose one machine in a sequential process can process one widget at a time while t he next machine, M2, is capable of handling n widgets simultaneously. Do we wait until the first machine has done n widgets and then load M2 or do we load M2 every time one widget is available?"
Here the tradeoff is between two constraints. Is it better, at this point, to satisfy due-dates by processing widgets through M2 even when it is under-loaded or should some due dates be compromised in order to achieve efficient machine utilisation? Without a view of future consequences of a decision it is difficult to weight alternatives. When combined with the combinatorial aspect this lack of knowledge about the ultimate consequence of a decision is called "scheduling uncertainty"

Uncertainty

Thirdly, it is obvious that any effective scheduling system should be able to adapt to unforeseen events. Just as interruptions in the form of phone-calls or requests from your boss will destroy your carefully scheduled day, so machine breakdowns, rush orders, personnel absences, etc, can invalidate a shop floor schedule. This feature of scheduling problems is called "environmental or executional uncertainty" In the worst cases the job-shop may have to be completely rescheduled. Usually this process is too slow to be useful and it would be more acceptable to reschedule only the affected parts of a schedule. Again this is a problem since it is difficult to identify where patches are required, and it is hard to update the schedule quickly enough for a reactive system.

FootNotes

**A non-deterministic algorithm is one which, in addition to all the usual features of algorithms, is capable of making an arbitrary choice between two alternative direc tions in which to branch, (Karp '75)

References

  1. CONWAY, R.W., MAXWELL, W.L. & MILLER, L.W. (1967) "Theory of Scheduling", Addi son-Wesley, Reading, Massachusetts.
  2. GONZALEZ, T. & SAHNI, S. (1978) "Preemptive Scheduling of Uniform Processor Systems", Journal Association for Computing Machinery Vol.15, pp92-101.
  3. COOK, S.A. (1971) "The Complexity of Theorem Proving Procedures", Proceedings of 3 rd Annual ACM Symposium on the theory of computing, pp151-8.
  4. KARP, R.M. (1972) "Reducibility among Combinatorial Problems", in Miller, R.E & Thatc her, J.W. (eds), Complexity of Computer Computations Plenum Press, New York.
  5. KARP, R.M. (1975) "On the Computational Complexity of Combinatorial Problems, Netw orks Vol.5, pp45-68.
  6. RICKEL, J. (1988) "Issues in the Design of Scheduling Systems", Proceedings of Confer ence on Expert Systems and Intelligent Manufacture, pp70-89.

Back to SWIM Project Page
Back to AI Center Home Page
Back to SRI International Home Page

Pauline M. Berry berry@ai.sri.com
Last modified: 2/10/98