Let's try our next one. Now we don't want to just have one machine, we want to have multiple machines. Let's say I want to schedule n jobs on m parallel machines. In this graph, we can see m is 3, n is 8. We are scheduling eight jobs to three machines. Again, we have the index set for a job. We have job one, job two up to job n, and they have processing time. We call each p_j. A job can be processed by any machine, but it can be processed on only one machine. If you schedule job one on machine one, then there's no way for machine two and machine three to help in processing job one. Job one belongs to machine one. Now the thing is that again, different schedules gives this machine different completion time and now what we want to do is to minimize makespan. There are two definitions for make span. Either you count the completion time for all the jobs and then find the one that has the latest completion time, that's one thing. Another thing is that for each machine, you count the completion time and to the find the last one. Basically it is the same, latest completion time for job or latest completion time for machine. Pretty much that's the same. That's our target, we want to minimize makespan or we want to balance the loading for all the machines. We want to make sure that all the machines pretty much are doing a similar amount of work. Now let's try to formulate this problem. We want to minimize makespan. As long as some jobs are assigned to a machine, now we know the sequence on that machine does not matter because we only care about when is the last job finished, and then there's no reason not to start your next job once you complete this job. Pretty much we may understand on each machine, I'm given the assignment. How may we calculate it's final total processing time? Let's see this. When we want to minimize makespan, pretty much all we need to do is to do job assignment. We don't need to do job sequencing on each machine. We don't care about the sequence. I hope that makes sense. To do assignment for job j and the machine i, let's say x_ij is one, if job j is assigned to machine i, so somehow that makes sense. Then for machine i, the last job would be completed at this particular time moment. This labels, which job is assigned to myself? Then for each job, if it is assigned to me, then I collect its processing time, and then the sum of all these processing times, is the completion time for myself. That's one thing. This is pretty much an expression for machine i. For machine, this is the completion time. Now we know we have the definition for makespan. Makespan let's call it w. Makespan is the maximum completion time among all machines. If you have several machines, their completion times 50, 90, 60, 80 and so on, and you say, you have value, call it w, which is your makespan, then very naturally you to have this constraint for each machine i, we know the makespan is not going to be smaller than the machine completion time because that violates the definition for makespan. Now let's collect everything. We want to minimize our makespan and we know for makespan, it satisfies this condition. The makespan is greater than or equal to the machine completion time for each machine, and also for each job, it must be assigned to exactly one machine. Then finally, this things are binary. We're pretty much done with this formulation. The only question that remains is that, how may we ensure that w is indeed the makespan. Why do I ask this question. Consider this example. Suppose I have three different completion time. The completion times are here, which may be calculated by taking a look at p_j and the x_ij. If they have this machine completion times, this particular constraint is saying that your w cannot be here, your w cannot be here. Why? Because if your w is here, for example, then it does not satisfy this constraint for the second machine. Your makespan must satisfy these constraints, but is the other way true? When you have a value satisfying all these constraints, is it guaranteed to be a makespan? Well, probably you would say it's not, because if all these machines finished at 60, 80, and the 90, we actually may set w to be 100. It still satisfy all these constraints. Maybe you would be confused about why we say this is a complete formulation. The answer is here, because you are minimizing your w. If you say w is 100, in this case, there is no way for your w to be 100 actually, because the minimization objective function is going to cut down w as much as possible until w equals to the maximum of these machine completion times. With this clever design, we may use this part to specify the makespan, and the minimization problem naturally helps us to formulate this problem by considering the objective function and the constraints at the same time. This is about makespan minimization on parallel machines.
