I'm stuck on modeling this problem...

You own a machine shop with 4 machines which all have the same processing speeds. You also have a set of 15 jobs. No job can be interrupted once it starts nor can a job be simultaneously processed on two machines. The processing time for job j = $P_j$. Your objective is to minimize the total completion time, that is, the sum of the completion time for every job.

I tried using an $x_{ij}$ decision variable where $x_{ij}$ $= 1$ when machine i processes job j. I got stuck on that because I had no way to determine the order that jobs were processed. I then tried to make an $x_{ijk}$ variable where $x_{ijk}$ $= 1$ if job i is the kth job processed on machine j. I can't figure out the constraints when I do it that way, though.

Note: I know how to solve this problem. Simply process the shortest jobs first on each machine. I am concerned about being able to model it as an integer program.


Here is what I have come up with: $C_{i,j}$ = the completion time of job in slot i on machine j. $x_{i,j}$ = 1 if machine j does job i.

Minimize $$\sum_{i,j} C_{i,j}$$

s.t. $$C_{i,j}= C_{i-1,j}+x_{i,j}*P_j, \forall{i} \forall{j}$$ $$\sum_{j} x_{i,j}= 1, \forall{i} $$ $$\sum_{i} x_{i,j}= 1, \forall{j} $$

  • $\begingroup$ Something like $\sum_{i}x_{ijk}\leq1$ for each $j$ and $k$ ensures that each machine is only working on one job at a time, and $\sum_{j,k}x_{ijk}=1$ for each $i$ ensures that each job gets processed once. I think those are sufficient constraints. prubin's suggestion to add dummy jobs will make calculating the objective function easier, and means you can change the inequality in the first constraint to an equality. $\endgroup$ – David Feb 8 '18 at 18:46
  • $\begingroup$ Those are the two constraints I'd gotten today as I worked through it. I feel like I still need another constraint to somehow define the completion times of each job, though. You think it can all be done in the objective function? @David $\endgroup$ – BrianW Feb 9 '18 at 3:00
  • $\begingroup$ Update: I've been trying to figure this out all night and I am stuck.. $\endgroup$ – BrianW Feb 9 '18 at 5:07
  • $\begingroup$ Yes, you can calculate the overall time as $max_{j}T_j$ where $T_j$ is the sum of completion times for jobs on machine $j$. With 15 jobs on each machine, $T_j$ will be the sum from $m=1,...,15$ of $m$ times the processing time for the $m$ job in order to start. (Since the completion time of the second job is the processing time of jobs 1 and 2 added together). Writing this out isn't trivial, but it can be done if you're careful. $\endgroup$ – David Feb 9 '18 at 17:58

The sum of the completion times is a very odd objective function. I wonder if perhaps you're misreading the problem (or perhaps it is misstated).

At any rate suppose that you create 45 dummy jobs with 0 durations. Set up 15 slots on each of the four machines, and assign your sixty jobs (15 actual, 45 dummy) to those slots. The completion time of the job in slot $i$ on machine $j$ is the completion time of the job in slot $i-1$ (0 if $i=1$) plus the processing time of the job in slot $i$.

With a little bit of algebra, you can directly express the cost of assigning any job to any slot as a function of the processing time $P_j$ and the slot index $i$. From there, I think you can solve it as a transportation problem (or an assignment problem if you don't lump all the dummy jobs into one category), meaning you should not need integer programming to solve it.

  • $\begingroup$ thanks for the feedback. Does that imply I only need a decision variable with two subscripts? And yes, it is a weird objective. The problem had two parts: one to minimize the makespan and this one to minimize the sum of completion times. $\endgroup$ – BrianW Feb 9 '18 at 1:38
  • $\begingroup$ Yes, if you number the slots 1 through 60, you only need one variable with two subscripts. In fact, you can get by with fewer than 60 values for that subscript (how is left to the reader as an exercise). Reducing the dimension of that second subscript (correctly) will speed up solution. $\endgroup$ – prubin Feb 9 '18 at 15:26
  • $\begingroup$ That only works if you have the jobs sorted from smallest completion time to largest, though. Right? I’m trying to do it without sorting them. $\endgroup$ – BrianW Feb 9 '18 at 17:15
  • $\begingroup$ No, I'm not assuming any sorting. However, it does require that the dummy jobs be assigned to the earliest slots, which I believe should automatically be the case in the optimal solution (so no additional constraints required for that). $\endgroup$ – prubin Feb 9 '18 at 21:33
  • $\begingroup$ Hm...maybe I'm more confused than I thought. Haha. Could you look over your notation in your original answer to this question? $P_j$ confuses me when the processing time is dependent upon the job (slot in this case, I supposed) and not the machine. $\endgroup$ – BrianW Feb 9 '18 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.