Okay, so our next topic is about machine scheduling. So that's the mastics. In many cases, the decision to do is to assign jobs or tasks to machines or agents. So as an example, suppose that you have a factory and then you are producing one product for multiple customers. So for example, you are producing desks or you are producing tables or whatever. You have multiple customers they order from you. So, the thing is that you may do one job at a time and each job has its due date, okay? So, you somehow want to satisfy all the demands all the orders by the due time. But maybe you don't have that amount of capacity. So you need to somehow determine how to schedule, or how to order sequence your jobs to minimize the total amount of delay jobs. Okay? That's one possibility. So you want to make sure that you make satisfied demands as much as possible. And maybe your decision is to this one. So, in this particular example, scheduling somehow means sequencing because you have pretty much one machine and you have multiple jobs, you need to order these jobs. And then that order is going to determine the completion time for each job, you compare those completion time and the due time, you may determine whether a job is delayed or not. So, in that particular case, there may be a bunch of ways to sequence your own jobs right? Basically you have n factorial. So somehow we cannot enumerate all the possibilities. Maybe, formulating this problem as an integer program and use the solver may help us solving this problem. Okay? So pretty much the problem of doing this kind of job scheduling, is typically referred to machine scheduling, even though sometimes we schedule these jobs to, for example agents, to workers, but in general we call them machine scheduling problems because at the beginning this problem is originated from factories. So there are all kinds of machine scheduling problems. They may be categorized in multiple ways. For example, you may have a single machine or you may have multiple machines, okay? If you only have a single machine then pretty much what you need to do is to determine the order of all those jobs. If you have multiple machines then there are also three different situations. The first situation is parallel machines, okay like in this example. Pretty much, you have eight jobs. You need to assign these eight jobs to three machines. For example, machine one is taking jobs 1, 4, and the 7 and so on. So once a job enters a machine and is processed by a certain amount of time, it will leave the system and then it's done. So each job has only one stage. In many cases, we are talking about flow shop problems. So that happens if a job has multiple stages like this, stage one, stage two and stage three, you need to go through several processes or several machines and each machine is responsible for doing one specific task or one specific stage okay? For example on this may be cutting whatever, this may be boiling something and then this may be packaging so, if all your jobs pretty much goes through the same order of machines, we call this a flow shop. So that's the typical production line. Problem in that case in a typical factory you have flow shops. It's also possible that we have job shop problems, in that case each job has different orders to go through, and a job may even need to go back to a particular stage to do the things again. So, you may somehow say job shop is a more flexible situation. We may also determine whether a job may be split or not. If a job cannot be split that basically means you need to start once you start a job, you need to finish it. Then you can do your next job and then you can do your next job. But sometimes what is required or what is allowed is that, you first do a job for example job A, and then because job B is considered more emergent. So you stop job A at this particular moment and try to complete job B, and then you resume job A. So, if that's the case, we say you are talking about a preemptive problem, you allow preemption okay? So if you do not allow preemption then this is not allowed. Once you start to do A, you need to finish it. It also may be categorized according to performance measurements. Sometimes we talk about the so called makespan. That's the time for your last job to be completed okay? Sometimes we talk about total completion time, for each job there is a time that the job leaves the system and is finished. We want to some of them so that we try to finish all the jobs as soon as possible. We may talk about a number of delayed jobs, total lateness, total tardiness and so on, and so on, and so on. So lateness and tardiness looks the same but a little bit different. Tardiness basically means, if your job is tardy, it's completion time is after the due time. And then tardiness is the difference between the completion time, and the due time. So suppose this is the due time, this is your completion time, then in that case, this particular amount is your tardiness. So the difference between lateness and tardiness is that if a job is completed before the due time, we still count this difference, and to say the lateness is negative. But when a job is completed before the due time, we would say there is no tardiness. So the tardiness would be zero. So that's somewhat different. So we don't really have time to give you a very thorough introduction to machine scheduling problems. What I just did in this particular video is just to show you that, there are all kinds of machine scheduling problems. Some can be easily written as an integer program, some are not. But later we will show you several examples showing you that, okay, some machine scheduling problems may be formulated. And then while we introduce those videos, we give you some more practice about integer programming formulation.
