# upper bound of makespan in resource constrained project scheduling problem

 1 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 eivazy 71●3●8 accept rate: 0%

One Answer:
 2 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 ♦♦ 14.6k●5●13 accept rate: 19%
Your answer
 toggle preview community wiki

### Follow this question

By Email:

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

By RSS:

Answers

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

Tags:

Asked: 26 Feb '13, 16:12

Seen: 1,700 times

Last updated: 26 Feb '13, 18:01

### Related questions

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