Resource Constrained Project Scheduling such that tasks are scheduled based on highest priority

Question

This is regarding a Resource Constrained Project Scheduling Problem (RCPSP). This involves scheduling certain tasks in time windows on machines subject to availability of manpower. This is set up in the form of an Integer Program. I'm using a uniform discrete time representation.

The decision variables are x_it: x_it = 1 if activity i is scheduled to start at a discrete time point t.

Every task has a priority associated with it due to external reasons. To illustrate the goal, consider 3 tasks - p1,p2,p3 with priorities 3,3,4. (two priority levels - 3,4) The requirement is this - if sufficient manpower is available to schedule p1 & p2 or p3 alone, p3 must be chosen even though p1+p2 > p3. I'm looking for a way to implement this logic using decision variables x_it.

I've tried implementing my requirement in the following manner: Assign a new priority (P) to each task: P1 = 3, P2 = 3, P3 = 7; Essentially this involves scaling each priority level such that no combination of lower priority tasks can be higher than this priority level and setting the objective function to "maximize P_i*x_it"

The problem with this approach is that while scaling for a large set of tasks (~300 tasks) and multiple priority levels (20 levels), the new priority values quickly become huge numbers (~10^17).

Is there a more robust way to implement this requirement within the Integer Programming paradigm?

Answer 1

One way would be:

1. Solve for jobs with highest priority (say priority 1). Let number of jobs schedule be n1.
2. Add constraint: scheduled number of jobs with priority 1 = n1
3. Solve for jobs with priorities 1 and 2. Let number of scheduled jobs with priority 2 be n2.
4. Add constraint: scheduled number of jobs with priority 2 = n2 etc