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 26 Feb '13, 16:12

hesam%20eivazy's gravatar image

hesam eivazy
accept rate: 0%

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%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 26 Feb '13, 16:12

Seen: 1,700 times

Last updated: 26 Feb '13, 18:01

OR-Exchange! Your site for questions, answers, and announcements about operations research.