Hi, I am modeling an underground mine scheduling problem which is like a resource constrained project scheduling problem with objective function of MAX NPV (instead of MIN makespan). In my problem makespan is not known. so I need to consider a reasonable upper bound for the makespan. I tried to find research works on upper bound of makespan but i could not find anything. Can you please guide me to papers,books,.... that may help me?
asked 26 Feb '13, 16:12
One issue with an upper bound for makespan is that you can always increase makespan by inserting slack in the schedule. So you need some idea of what an unreasonable amount of slack would be. One possible criterion would be that slack should never result in all resources being idle simultaneously (but I'm not sure that's a good criterion).
If you can come up with criteria for "reasonableness", you could try solving a separate model that maximizes makespan (ignoring NPV) subject to precedence and resource constraints as well as enforcement of "reasonableness". That would give you a plausible upper bound.
You could also take a parametric approach. First solve the minimum makespan problem (ignoring NPV). Let \(T_0\) be the minimum makespan obtained. Now solve the NPV problem with an upper bound of \((1+\lambda)T_0\) for various values of \(\lambda\ge 0\).
answered 26 Feb '13, 18:01
Paul Rubin ♦