-1

I have a Operation Research Problem in which the aim is to reduce the completion time of projects. For explanation: consider I have projects as A, B, P1, P2, C. Such that projects A, B are inputs to project P1; and projects C, P1 are inputs to project P2. A project can start only when all its inputs are available. Project A finishes at 10pm; project B finishes at 11pm; project P1 finishes at 12pm; and project C finishes at 11:15pm. Thus project P1 is bottlenecked by Project B -- as it is the last to finish. Similarly project P2 is bottlenecked by project P1. Also each of the projects have a saving in time s(i). Each project has a budget bi. I want to choose a set of projects which maximize savings with the constraint that the added budget of these projects is less than B.

Jannat Arora
  • 109

1 Answers1

1

This model is nonlinear. I believe it's also incorrect, i.e., it wouldn't give you meaningful results even if it could be solved. Here are the problems that I see:

  1. $x_i$ and $s(i)$ are both decision variables, and they are multiplied by one another in the objective function, so the objective is nonlinear.
  2. The constraint $s(i) = \max_{j->i} s(j)$ is nonlinear because of the max. I'm also not quite sure how to interpret the max; are you saying take the max over all inputs $j$ of $s(j)$?
  3. There are no constraints linking $x_i$ and $s(i)$. So, right now your model would set $x_i = 1$ for as many $i$ as possible, and then set $s(i) = \infty$ for those $i$ -- your model will be unbounded.
  4. I might be misunderstanding $s(i)$ -- is it actually a parameter (input), not a decision variable? If so, the last constraint should be omitted. You shouldn't have constraints that only involve parameters. If you need to impose conditions on the parameters, that should be done when developing the inputs to the model, not in the model itself.
  5. I'm also not sure this model would reduce the "bottlenecks" in the schedule. For example, suppose we have a long path from A to C that has very little opportunity for savings, and another slightly shorter path from A to C that has lots of opportunity for savings. Your model will choose the projects on the second path, even though it will not actually reduce the completion time of project C at all.
LarrySnyder610
  • 1,131
  • Thanks for your answer. I have improved my answer. How can I introduce a constraint to answer 5 -- i.e. reduce bottleneck in the schedule. Also s(i) is a variable – Jannat Arora May 28 '19 at 20:22
  • I don't know. That's a whole separate modeling question. Have you looked into the literature on scheduling problems? Probably there are similar models in that literature, or if not, then at least those models can serve as a starting point for yours. – LarrySnyder610 May 29 '19 at 00:21
  • I did look into literature but could not find any – Jannat Arora May 29 '19 at 00:31
  • OK, sorry to hear that. I don't think there's a simple answer to "how to resolve #5", especially because there are other problems with the model (like nonlinearity). I don't think we can just formulate a new model for you; hopefully you can make some progress on your own, and post a new question here if you get stuck on a specific issue. – LarrySnyder610 May 29 '19 at 00:37