# Job Shop Optimization — Minimize Total Completion Time

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.

UPDATE:

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}$$

• 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. – David Feb 8 '18 at 18:46
• 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 – BrianW Feb 9 '18 at 3:00
• Update: I've been trying to figure this out all night and I am stuck.. – BrianW Feb 9 '18 at 5:07
• 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. – David Feb 9 '18 at 17:58

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.
• 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. – BrianW Feb 9 '18 at 21:46