I want to bind a classical project scheduling problem with Cmax objective function. For example, the first and the second activity can start at the beginning of the project. I want to limit the model in which 1st and 2nd activities never run at the same time. But I don’t know which one is scheduled earlier. Moreover, in my model, just these two activities use the same resource. This resource is bounded, hence model is a special case of RCPSP. How can I handle the resource constraint on my model?
If you really only have one pair that can't run simultaneously, solve your model twice, once with 1 constrained to precede 2 and once vice-versa. If you have a lot of pairs, model your problem as a mixed integer program with binary variables controlling
which job in a pair finishes before the other starts.
-cat
Just for the record, this is exactly the type of problem that the classical project scheduling model is designed to solve (for a very thorough coverage, see Herroelen and Demeulemeester 2002, Project Scheduling: A Research Handbook). Resource constraints are at the heart of the issue. In your example, you would define a resource with one unit of capacity that is required by both activities at a level of one. (In general, there may be many other resources with different capacities that apply to other subsets of activities, each of which requires different levels of capacity, such that the total capacity utilized at any time cannot exceed the resource capacity. Some activities may require more than one resource.) As such, it can indeed be formulated as an mixed integer program but only very small problems can be solved that way. A branch and bound approach is better, but real-life projects are typically too large to yield to B&B either. If you decide to resort to heuristics, there are many competing approaches, usually based on a search tree that is similar to the search tree of a B&B but using priority rules to curtail the branching.
- Badges
- Science topic
- Similar topics
- Engineering
- Modeling