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? Thanks Hesam
asked
hesameivazy |

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 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
Paul Rubin ♦ |