Let's try this particular machine scheduling problem. We have one machine, and we are going to schedule several jobs. We want to count their total completion time and do the minimization. We're going to schedule n jobs on a single machine. Let's say the set j is the index set for all jobs, and then each job j has a processing time, we denote it as p_j. Naturally, p_j is a positive number. Different schedules is going to give these jobs different completion times. Even though we don't have specific definition for completion time, basically, it's the time that after you start a job, after this amount of time, you complete that. So it's just that very intuitive definition. We were going to denote the completion time of job j as x_j. Pretty much that says x_j is a decision variable. If that's the case, x _j is something to be determined. But we cannot determine x_j randomly by ourselves. There must be some constraints related to p_j and is determined by the order for us to process all the jobs. The machine can process only one job at a time. We aim to schedule all the jobs to minimize the total completion time, which can be written in this way. To solve this problem, let' try to use x_j as our decision variables. Somehow, we can decide x_j, but that is subject to the fact that jobs cannot be conflicting with each other. Let's consider this particular order, which means we schedule jobs 1, 2, 3, 4, 5 until n in this specific order. We just sort jobs according to their job ID. In that case, we may take a look at this Gantt chart. This is going to help us understand what happens. We start at time zero and then spend p_i amount of time to finish job 1 at time x_1. Then we start to work on job 2 at X_1 and to have it finished at x_2. Naturally, x_2 would be p_1 plus p_2. Then naturally for x_3, it's going to be p_1 plus p_2 plus p_3, and so on. This somehow gives us a hint saying that, well, if we are going to schedule this problem, then pretty much what we need is that if we say a job is in front of the other job, or if a job is after another job, then their completion times must be far away from each other enough. They somehow need to be separated by at least the processing time of that particular job. If you consider job 1 and job 2, you can see that the difference between x_1 and x_2 must be at least p_2. If you consider x_1 and x_3, pretty much when you are doing the scheduling, you don't really know whether there will be anything else that is within job 1 and job 3. But you know for x_1 and x_3, their difference must also be at least p_3 and so on. As long as we know job b is after job a, then their completion time must be separated by at least p_b or something like that. That makes sense. But the thing is that, we need to consider two things. First, splitting jobs, does that help? I would say it does not help. In this particular scheduling problem, if you are allowed to schedule jobs by having preemption, by having jobs splitting, then that's not going to help you to finish these jobs sooner than having no splitting. You may think about this by yourself, but that's assumed preemption is not allowed in this particular example. Now, let's consider the second question. Pretty much we mentioned to you that if job 2 is after job 1, we know there must be a difference between their completion time. If job 3 is after job 1, if job 3 is after job 2 and so on, we may typically write down a constraint like this. The difference between x_2 and x_1 must be at least p_2. But before you really find an optimal schedule, how may you know whether job 2 should be before or after job 1? Actually you don't know. There must be some ways to deal with this. Well, we're lucky because we have learned it. In a feasible schedule, we all know that either job i or job j is the one that is scheduled earlier. In that case, all we need to do is to say, okay, we have two constraints. The first one is the separation constraint, saying that job j is the later one. The second one, we are saying that job i is the later one. Either i is later or j is later. We may introduce a binary variable z_ ij. If job j is before job i, we say z_ij is 1. Then we write down these two constraints. That's going to help us choose one of them to be satisfied. Choose either this one or that one. Let's take a look. If z_ij is 1, then this part is going to become 0. We know x_i is going to be greater than or equal to x_j plus pi. That means your job i is here, job j is there. You're somehow guaranteed that xi is going to be late enough. On the contrary, if your z_ij is 0, then it's going to become x_j is greater than or equal to x_i plus p_j. In that case, it's first job i and then job j. Pretty much we can say, this is to allow job j to be completed late enough. Somehow i is in front of j, or j is in front of i. Either one must be satisfied. Our variable z_ij would help us to satisfy one of these two constraints. The last thing regarding these constraints, is that our M must be specified a value. I would argue in this way, for this particular left hand side, we know is less than or equal to xi plus p_j. Because that minus x_j, must be less than or equal to 0. That's one thing. Then for this particular thing, we may also say that, x_j cannot be greater than or equal to the sum of all your processing times. Then we may also consider this p_j again. For this particular constraint, maybe we would set M to be this particular amount and multiply it by z_ij. I would say this is the upper bound. If you consider the upper bound as this one, then there will be no trouble with you. I'm going to leave a question to you, whether you may set M to be the sum of p_j. If that's possible, somehow it should be related to this minus x_j. Maybe you want to think about it, but I'm not going to tell you the answer directly in this video. If you are able to find some answer, that would be great. If you cannot, it's still fine because you may at least use this particular upper bound to be your value for M. In summary, we have the complete formulation here. We try to minimize the total completion time. We use these two sets of constraints to ensure that the processing of different jobs do not conflict with each other. We have non-negativity constraints, we have binary constraints. Now we want to spend some time to discuss the last one. Why do we need this constraint? Pretty much this is saying that your x_j is greater than or equal to p_j. It seems to be a weird constraint because of course, it should be true. Even if you start your job j at time 0, you still cannot finish it before time p_j, right? This makes sense, but the question is whether we really need it. Let's say we remove it, so there is no such constraint, what will be your optimal solution? I would say, somehow there must be a schedule. Eventually there must be a schedule. If there is a schedule, then this should be x_1, this should be x_5, and so on. You will see that there is nothing that prevents us from setting x_1 to be 0. If we don't have this constraint, naturally, we would set the first job to be finished at time 0. That's why we need this constraint x_j to be at least p_j. We have no idea which one would be the first one, so we impose this restriction on all jobs. That's how we complete these formulation. In fact, there is an algorithm to optimize this schedule, or maybe you want to think about it. But that's beyond the scope of this course, so I'm not going to talk about it. The thing is that, this problem itself seems to be easy, but it becomes even harder if you have something called release time. What's release time? Release time says, "A job is going to be released sometime later." For example, if R_j is the release time of job j, you may start to do job j only after R_j. It's just like if your instructor give you some homework assignment, if he will announce the assignment next Monday, you cannot start to do it before next Monday, and that's the release time. Challenge yourself by thinking about this, if you know the release time for all the jobs, how would you add this constraint into the model? Think about this, try it as your exercise. I'm going to stop here about the single machine completion time minimization.
