1
$\begingroup$

I have a scheduling problem to solve. It's a resource-constrained project scheduling problem with time-varying resource availabilities. The objective is minimizing tardiness. The full detailed model is given here.

I implemented a heuristic based on a priority rule: At each step, the set of tasks can be divided to 3 sets: the set $A$ of already-scheduled projects; the set $B$ of "schedulable" tasks (tasks whose predecessors are already scheduled) and the set $C$ of tasks not "schedulable" yet. At each step, we compute the priority of tasks in $B$ and select the one with the highest probability. It's then scheduled at the earliest possible time when there is available resources.

However, I want to find a way to somehow deal with this "infeasibility"case. enter image description here

Remark: the green lines are the availabilities of the resource, Task A in blue is scheduled and task B in grey is not scheduled because it requires two units wheras only 1 unit is available.

If the task A is scheduled first (because it has the highest priority), there will be not enough resource for the task B. Thus, by the end, not all the tasks are scheduled (task B is not scheduled). However if I've scheduled B first, it will be o.k, since task A requires only one unit, and by the end all the tasks will be scheduled.

PS: Finding a feasible solution is NP complete in this case.

Improve this question
$\endgroup$
2
  • $\begingroup$ Infeasibility really has nothing to do with the algorithm. It is a property of the problem statement. The algorithm (math programming/heuristic/etc.) may or may not be able to solve a feasible problem, but that is a separate issue. It isn't really possible to give good advice on #3 and #4 without diving into the code, but some kind of local search is probably needed and it sounds like you are on your way to writing some kind of genetic algorithm, which can be very effective on these types of problems. $\endgroup$
    – AirSquid
    Commented Jul 25, 2020 at 17:39
  • $\begingroup$ @AirSquid by infeasibility I meant the algorithm get stuck somehow and can't schedule all the tasks which doesn't mean that any other algorithm can't find a feasible solution or some "backtracking" can't find a solution. $\endgroup$
    – Joffrey L.
    Commented Jul 25, 2020 at 17:58

2 Answers 2

Reset to default
3
$\begingroup$

I'm not sure there is a way to tweak your heuristic that will guarantee finding a feasible solution (assuming one exists). What you might try is a restart approach combined with a modification of your priority assignment method. Let's say that the modified heuristic assigns each task a "base" priority and then adjusts it when computing priorities for group B tasks. If the heuristic finds itself blocked as in your diagram, it increases by some specified amount the base priority of the task that cannot be scheduled (and maybe increases the base priorities of predecessor tasks as well), then scraps the schedule under construction and starts over.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 0. How to decide about the quantity of adjustment, if a task is unscheduled do I need to guarantee that its priority is higher than any other task? 1. Can a time analysis (i.e compute the earliest and latest start time for each task) be helpful to remove some of the blocking cases ? 2. Assuming I do this and still have some unscheduled tasks. When I do a local search, how to consider those unscheduled tasks ? $\endgroup$
    – Joffrey L.
    Commented Jul 26, 2020 at 22:39
0
$\begingroup$

Infeasibility, in many cases, back to the structure of the problem under study and as @AirSquid mentioned too, it really has not related to the solving algorithm if, it was implemented correctly. One of the good approach to deal with the infeasible problem is adding the slack variables to the constraints and setting the high-value objective coefficients for them. Would you see this link? I hope it will be helpful.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for the link it helps a bit but I am not sure if I well explained my problem. I've added an example, would you mind taking a look? $\endgroup$
    – Joffrey L.
    Commented Jul 26, 2020 at 9:09
  • $\begingroup$ @JoffreyL., would you say please, do you have an MP/CP formulation to do that or you only try to find a feasible solution by a metaheuristic method? $\endgroup$
    – A.Omidi
    Commented Jul 26, 2020 at 9:44
  • $\begingroup$ I've added a (new) detailed link to the model. (I included the pre-processing I am doing) $\endgroup$
    – Joffrey L.
    Commented Jul 26, 2020 at 10:35
  • $\begingroup$ @JoffreyL., it seems, I could not access to you mentioned link!!! $\endgroup$
    – A.Omidi
    Commented Jul 26, 2020 at 11:56
  • $\begingroup$ Sorry, I updated the link. $\endgroup$
    – Joffrey L.
    Commented Jul 26, 2020 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.