IBM ILOG Scheduler User's Manual > Advanced Concepts > Advanced Features and Concepts > Scheduling Algorithms |
Scheduling Algorithms |
INDEX
![]() |
Before you start studying the examples in Part II, , we want to say a few words about scheduling algorithms. For the problems in Part I, , very simple algorithms are used to solve the problems. In fact, for the first problem, an exact algorithm exists for computing an optimal solution without backtracking. Later problems, in contrast, necessitate a search for optimal solutions.
The most important variables of a scheduling problem are, in most cases, those that represent the start times and the end times of activities. Picking a constrained variable and setting a choice point at each of its values is not an efficient method for exploring the search space because, in most cases, changing the start or the end time of an activity from a value v
to a value v-1
or v+1
has little or no effect on the quality of a solution.
This part presents more efficient algorithms for exploring the search space. Indeed, Part III, focuses on search. Many of the algorithms presented in this part should be taken only as starting points. Often it is a good idea to think about problem-specific heuristics that can be used to solve your problem. Furthermore, when reusing an algorithm, you should check whether the algorithm really solves the problem. For example, the algorithms used in the chapters dealing exclusively with unary resources determine only an ordering of the activities on each of the resources. If you add constraints that require the exact placement of the activities in time, that ordering algorithm will not suffice.
You should also be careful when combining algorithms. Some algorithms are based on scheduling one resource at a time, whereas the algorithms used for scheduling discrete resources are based on scheduling forward in time. For a problem in which both unary and discrete resources are used, you could simply use the algorithm for the discrete resources, as a unary resource is just a discrete resource of capacity 1. If a simple ordering of the activities for the unary resources would suffice, you could also combine the two kinds of algorithms by first scheduling the unary resources, and after that, scheduling the discrete resources. If you do that, you have to pay close attention to separating those activities that use the unary resources and those that use the discrete resources. If such a separation is hard to carry out, then we recommend using the algorithm for discrete resources.
Again, we stress that you should take the examples in this part only as a starting point. The more you get acquainted with Solver and Scheduler and with the problem you are going to solve, the better you will be able to implement an algorithm that suits your problem.
© Copyright IBM Corp. 1987, 2009. Legal terms. | PREVIOUS NEXT |