# How to correct this scheduling algorithm?

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. 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.

• 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. Jul 25, 2020 at 17:39
• @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. Jul 25, 2020 at 17:58