In today's lecture, we will continue our discussion on integer programming formulations.
In the last lecture, we formulated the grouping problem as an integer programming problem.
Today, we will begin with something called the fixed charge problem, which is related
to the grouping problem but slightly different. Now, the problem is like this. Suppose there
are say three or four locations where somebody would like to establish a factory or a warehouse
or a distribution center or something like that; so these will be the central nodal points.
From this factory or distribution center we have to send items to different places. These
will be the customer points; this will be there and so on. There is already an established
connectivity saying, for example, this point is connected to this, this point is connected
here, this point is connected here, this point is also connected to this, connected to this,
connected here connected here and so on. We will have certain connectivity associated;
you have to make sure that every point is connected to at least one of these or more
than one of these and so on. For example, we will call these as i, these are the i's
and these are the j's, so we will say that there is a requirement of dj for each of these
j's and there is a capacity ai, we will look at that little later. There is a transportation
cost Cij of transporting it from i to j. There could be an ai, which is the capacity restriction
also. The most important thing is that, it is not that you have these plants located
in all these four places, what you want to do is, let us say, you want to locate p number
of plants, say p could be 2. Let us assume that these are candidate locations for plants
and these are the demand points and there is transportation from the plants or the factories
to the demand points. There are four candidate points but we want to locate it only in two
places, not on all the four. There is the fixed charge fi of locating something in location
i, that is also there. In order to create a facility I have a fixed expenditure which
is called a fixed charge; that is why this problem is called fixed charge problem.
The variables will look like this; you can have Yi = 1, if location i is chosen and Xij is the quantity transported from i to j. So your objective function for
this problem will be to minimize sigma fi yi plus sigma Cij Xij. You may say for example,
if there is an absolute connectivity every one of the j's is connected to all the i's
and so on, a complete connectivity between i and j then you may formulate this problem
for a fixed number. For example, you may say sigma Yi equal to p implies that I want my
factories to be located exactly in p out of the m possible locations; you could have that.
At the same time if you do not have this complete connectivity, what you would like to do is,
to have a minimum number of locations you will ignore this constraint and let the problem
decide the number of Yi�s that it wants to have. You may have this constraint you
may not have this constraint depending on the situation. You may also have Xij less
than or equal uij, which is the link. For example, this will be uij, which is the capacity
connected with the arc i-j. I may be able to transport the maximum of uij between i
and j.
If you do that then it is called a capacitated problem. If you leave out the capacity restriction,
then it becomes an uncapacitated problem. For example, the standard transportation problem
that you have formulated is an uncapacitated problem. It does not put any restriction on
the limit on Xij. All capacity constraints or capacitated problems have constraints which
are upper bound to that Xij. So you may have a capacitated problem, you may have an uncapacitated
problem. If you have a capacitated problem then you will get this constraint. If it is
uncapacitated, you will not limit the Xij, it can be anything. Sigma Xij should be less
than or equal to aiYi. If location i is chosen, which means Yi equal to 1, only then the ai
capacity is available for you to be distributed, otherwise it is not. The standard transportation
constraint would not have this Yi. It will simply be sigma Xij less than or equal to
ai, j is equal to 1 to n. Because of the location decision that comes along with the transportation
decision, you will have sigma aiYi. If you do not have this capacity constraint
ai and if you assume that the plant can produce an infinite number or whatever is needed,
then this will look like sigma Xij is less than or equal to M into yi, where big M is
large and positive and tends to infinity. When the location is chosen, it can produce
a maximum big M. If it is not chosen, it can produce only 0, so nothing can come out of
it. Sigma Xij is greater than or equal to bj because what is needed in destination j
should be met. All these will work very nicely if there is complete connectivity among the
i's and j's otherwise what you can do is, you can leave out those Xij�s for which
there is no connectivity; that is one, or you can set that uij equal to 0 so that the
whole thing does not exist, you can do that or you can even go back and put another aij,
which is like an incidence which models an incidence; aij equal to one if there is a
link between i and j, you can do that also and suitably bring that aij or bij. You should
not confuse with a and b. Call it some c; c is also used, so some number rij as an incidence
between i and j and use it suitably. So, Xij will be enabled only when that rij is 1 otherwise
it will not be enabled; you can do it that way. Easiest thing to do is put all the uij�s
to 0, where you do not have the link; that is the easiest thing and so on.
So Xij greater than or equal to 0. What is bj? bj is the requirement. What is that dj?
Where is the dj? I should be consistent. I will call this dj. So Yi is equal to 0, 1.
This is called a fixed charge problem. This is a very important problem in location, allocation,
distribution, supply chain and in all those areas, particularly when you are looking at
decisions at multiple levels, for example, you could have factories, you could have distribution
centers, you could have warehouses and then retailers. The problem will look like, I would
want to make say p1 out of M1 factories, p2 out of M2 distribution centers, p3 out of
M3 warehouses, p4 out of M4; M4 is ultimate customer so you will not have that; you will
get a series of fixed charge and becomes a fairly complicated problem. This is reasonably
similar to the grouping problem but it has additional constraints and restrictions.
We will look at some more examples of integer programming formulation. You will also take
the travelling salesman problem as the next example.
To begin with, let us take a travelling salesman problem, where the distance matrix is given.
We can generalize it to n there is a no problem at all, except that we need to consider the
case where n is odd and n is even separately. We will right now take five, where n is odd
and we will assume that we have the distance matrix that is given to us. Distance dij is
known. We can assume that it is symmetric but it is not absolutely necessary that it
is symmetric in a travelling salesman problem. Normally, distance between i and itself, any
point and itself is 0. But it is customary to define di,i as infinity in all travelling
salesman problems. So, we will put a dash here in all these five places, indicating
infinity. We will see why we do that very soon. In all travelling salesman problem you
can almost close your eyes and put infinity along the diagonal, you will never have a
0 in the diagonal. Let us define Xij equal to 1 if the salesman visits j immediately after i. There is one more aspect
which we will touch upon. Unless otherwise stated explicitly, it is assumed that the
travelling salesman distance matrix for any TSP will have to be square because it is distance
among the certain number of cities. It will be symmetric because it is under the assumption
that you are modeling Euclidean distances unless otherwise you are bringing some other
factor as a distance measure in a TSP. The third important assumption is it satisfies
triangle inequality. Triangle inequality means if you take three points i, j, k, dij plus
djk is greater than or equal to dik; I think strictly greater than is triangle inequality.
So you will have this. This comes from the fact that in a triangle sum of two sides is
always greater than the third. When you have this triangle inequality satisfied, it reflects
itself in a different form. If you define a TSP, the normal definition of a TSP is a
salesman starts from city 1 or any city, visits every city once and only once and comes back.
This once and only once comes in because if your matrix satisfies triangle inequality
you can prove that the person will visit once and only once. For example, you cannot have
a solution where the salesman visits a city twice other than the starting city of course.
If you assume the city 1 is the starting city, the salesman will start from city 1, go back
complete the circuit and come back to 1. Every other city in a TSP, he or she is expected
to visit only once and that comes because of the triangle inequality. If you satisfy
triangle inequality, any solution where the person visits a city more than once will always
be inferior to a solution where the person visits once and only once. So, that once and
only once comes because of the triangle inequality. Distances are positive, distances are more
Euclidean; therefore they satisfy this. For example, if you have a distance matrix that
does not satisfy triangle inequality, then it is always advantageous for you to go from
i to k and k to j instead of i to j. So the person will end up visiting a node more than
once.
For example, if I want to go from say 1 to 5, if going through 4 is cheaper I will always
do that. For example, from 5 to 7 I am going again and if it turns out that going through
4 is cheaper, I will visit 4 twice. But when this condition is satisfied I will never do
that. So that is one thing which we will assume unless otherwise stated that the matrix is
square symmetric and satisfies triangle inequality, which implies that the person will visit every
city once and only once. Let us go back and start formulating. The person has to leave
each city once.
Sigma Xij is equal to 1. From every i, he has to leave, so summed over j equal to 1
for every i; person has to enter every city so sigma Xij summed over i equal to 1 for
every j. Xij equal to 0 or 1 and minimize sigma dij into Xij. Let us assume that we
have formulated the TSP this way. Is this answer correct or is this formulation correct?
It is not, simply because this is the formulation for the assignment problem. There has to be
something more which makes it the TSP, so what is that? Suppose we look at this matrix
and we just apply this formulation saying that it is a TSP formulation and let us also
assume that we have not done this and we have used that the distance between any point and
itself is zero.
Now if you apply this formulation, what will you get? You will get all diagonal assignments,
X11 equal to 0, X22 equal to 0, z equal to 0. Why is it not a TSP, because it is not
a tour. Now number one is if you put 0s here, then your travelling salesman problem for
this formulation, which we will refine this formulation later we will give you all diagonal
assignments. Each of the diagonal assignment is a subtour. There are two things in a TSP.
If I have a 5 by 5, if I have 1, 2, 3 say 5, 4, 1 is a tour; it is a feasible solution
to the travelling salesman problem. For example, this will be reflected by X12
equal to X23 equal to X35 equal to X54 equal to X41 equals 1. There will be five allocations
and this will be the order of allocations, this has a tour. Suppose I have X12 equal
to X25 equal to X34 equal to X43 equal to X51 equal to 1; let us try to get a tour or
a subtour from it, then you get 1 to 2, 2 to 5, 5 to 1, 3, 4, and 3. This is not the
solution to the TSP, this is the subtour and there are two subtours. A solution to the
TSP should not have subtours, so what we need to do is, we need to add what are called subtour
elimination constraints into this and if you are able to do that, then we get the solution
or the formulation for a travelling salesman problem. So you need to add subtour elimination
constraints. For a travelling salesman problem of length n or size n, then you can have subtours
of length 1, 2, 3 up to n minus 1. You need to eliminate all these kinds of subtours.
Now, every subtour elimination constraint would involve a constraint and you want to
minimize constraints in any formulation. Now what you do is you put a dash here, which
is like a big M, so that you avoid subtours of length 1.
The moment you start putting infinity here or dash here, then Xii will not become an
allocation in a TSP. So indirectly you eliminate subtours of length 1 by forcing the diagonals
to infinity. That is the reason why you put infinity in the diagonals. You have eliminated
subtours of length 1.
Suppose I have a solution which is like this; X11 equal to 1, X25 equal to X52 equal to
1, X34 equal to X43 equal to 1. There are three subtours, 1 to 1 is a subtour, 2 to
5, 5 to 2 is a subtour, 3 to 4, 4 to 3; there are three subtours. This is the subtour of
length 1, this is the subtour of length 2, subtour of length 2. There are two links so
subtour of length 2. There is only one link so its subtour of length 1. Now by forcing
the diagonal elements to infinity we have eliminated subtours of length 1.
Now you need to eliminate subtours of length 2 and that will be like this; Xij plus Xji
less than or equal to 1 for all i and j. For i equal to 1, j equal to 2, actually you can
also put i not equal to j so that you can reduce some more constraints. If I look at
i2, I am trying to say X12 plus X21 less than or equal to 1. What will happen? One of them
will have to become 0. If X12 is in the solution, X21 will not be in the solution. If both are
not in the solution it is still acceptable to you. That is why I have put a less than
or equal to 1. It may turn out that both 1, 2 or 2, 1 may not be in the optimal solution.
Therefore you put a less than or equal to 1 or in general for a subtour of length k,
you put k minus 1. This will take care. The only problem is there are too many constraints.
There are nC2 or nC2 minus n if you leave out that i not equal to j, and you put nC2-n,
that many constraints you will have to put. If you add all these nC2, you have now eliminated
the subtours of length 2. Go back and look at subtours of length 3. When I have to eliminate
subtours of length 3, then I have to put Xij plus Xjk plus Xki less than or equal to 2,
which means I have nC3 constraints because i j k can be chosen in nC3 ways. I will have
another nC3 set of constraints and I will have another nC4 set of constraints.
The number of constraints becomes exceedingly large, but let us try to do something else.
Now, let us go and back look at this three constraints again. I have a TSP with five
cities. Let us assume I have a subtour of length 3. If I have a subtour of length 3,
the remaining two cities which are not included in my subtour can either form a 2 city subtour
or two 1 city subtour. It cannot form anything else; therefore, if I eliminate all 1 city
subtours and 2 city subtours, I am automatically eliminating all 3 city subtours. Is that clear?
I will repeat again. If I have a 3 city subtour in a 5 city TSP, then the remaining 2 cities
can become either a single subtour of length 2 or 2 subtours of length 1 each, no other
possibilities exist. Therefore, if I eliminate all 1 city subtours and all 2 city subtours,
I automatically eliminate all 3 city subtours, which I have already done. I do not have to
put this nC3. Similarly, if I have a 4 city subtour there is only one remaining and that
has to be a 1 city subtour. I have already eliminated 1 city subtours,
so I do not have to do the nC4. So in general, if I have n city travelling salesman, problem
where n is odd it is enough if I do till n minus 1 by 2. I do not have to do anything
beyond. If n is even, I will do up to n by 2. When I have 6-city TSP I have to necessarily
also eliminate the 3 city subtour, because a 3 can result in another 3. It can also result
in another 3, so you do it up to n by 2, when n is even and n minus 1 by 2, when n is odd.
You will have nC2 plus nC3 plus dash, dash nCn-1/2 constraints if n is odd in addition
to this 2n and nC1 plus nC2 up to nCn/2, when n is even in addition to these. You will realise
that the number of constraints itself is exponential, because nCn/2 or n minus 1 by 2 is exponential.
Number of constraints itself is exponential. Much later in the course when we look at TSP,
we will at least see that this nC1 up to nCn minus 2, which is an exponential number, can
be replaced by a set of n constraints or n square constraints. We will see that little
formulation much later, but right now the understanding is there will be whole set of
subtour elimination constraints, which we have to make. Much later we will look at that
formulation where we will have n square or nC2 or whatever number like that. nC2 constraint
which is capable of modeling the entire thing, that will be a more efficient formulation
of the TSP. The understanding here is to add this subtour elimination constraint; also
the understanding is that we do it systematically, so you can stop up to n minus 1 by 2, when
n is odd and n by 2 when n is even. We will look at another formulation now. We look at
job shop scheduling problem.
Let us say there are three jobs; there are three machines. You call the jobs A, B and
C, you call the three machines M1, M2 and M3.
Now let us say job A will have M1, M2 and M3. This will be the route. Job B will have
M2 and M1 and say job C will have M3 and then M2. The associated processing time will be
Pij, where i equal to 1 to 3 represents job, j equal to 1 to 3 represents machine. For
example, this will need P11, P12, P13, P22, P21 and so on. This is called the job shop
because the order of visit is different for different jobs. If for example, we say that
all the jobs will first visit M1 and then M2 and then M3, then it becomes something
called a flow shop, where all the jobs have the same order of visit. If the route or order
of visit depends or is different for different jobs then it comes under a general job shop
scheduling problem. All the jobs are available at time equal to 0. When we start processing,
each job will be completing at a certain time. For example, let us say all these three will
be over if they are over by certain time, say A1 and this is A2 and this is A3 or you
call it some capital C1, capital C2, capital C3.
What I want to minimise is called the makespan, which is the time at which all the jobs are
over. It is something like all the three jobs are to be done for the same customer. When
all the three jobs are finished I can pack them and send it to the customer. So I want
to send it to the customer at the earliest and this is what I want to minimise. I want
to find out how I schedule these jobs in the system such that I minimize this. C is the
time at which this is over. C is the time at which this is over; this is not given to
you C1, C2, C3 are not known. C1, C2, C3 will have to be found. The objective is to try
and minimize the make span, which is the time at which all the jobs are ready and over.
That is the objective. Now, let us formulate this problem.
Let tij be the starting time of job i on machine j.
For example I take job A. For this certain things are very clear. t12 from 1 it goes
to 2, so t12 is the start time of job A on machine 2. t12 has to be greater than or equal
to t11 plus p11 because job A first visits machine 1 and only then it has to visit machine
2, which means it should have completed its work in machine 1. If tij is the start time
on machine 1 for job 1, then t11 plus p11 is the time it is over and it can go to machine
2 only after this is over; this is very straight forward constraint. Similarly t13 is greater
than or equal to t12 plus p12, which is again a very straight forward constraint. As far
as this job is concerned t21 is greater than or equal to t22 plus p22. That is the only
thing I have and as far as this is concerned, t32 is greater than or equal to t33 plus p33.
For example, I can finish my stuff with M1. Any machine can process only one job at a
time that is an assumption. So, I may have to wait to get this M2. My start time t12
need not be immediately after this is over. This could be over, it could be waiting for
machine 2 and machine 2 may be busy doing something else, it waits and once the machine
2 is free, it can go, which means t12 is greater than or equal to t11 plus p11. These are simple
constraints which are easy to model. The difficulty comes here; if I take machine M1 then machine
M1 now has job A and job B going into machine M1. I do not know which one is going to go
first. I have to decide such that it is advantageous to me. What I will do is, if I take a machine
M1, either job A can go first and then job B can go or job B will go first and then job
A can go. You get into an either or situation. If you take M1, if job A goes first and then
job B goes, then it means that t21 job B going into machine 1, will have to be greater or
equal to t11 plus p11 or t11 is greater than or equal to t21 plus p21.
You have an either or constraint that comes in which we have not modeled yet in our linear
programme. We always know how to model the rigid constraints but not an either or constraint.
Similarly, if you take M3 it is either A and C. This is for M1. For M3 you will get a similar
either or constraint which will be like this. M3 has A and C, so you will have either t13
is greater than or equal to t33 plus p33 or t33 is greater than or equal to t13 plus p13.
You take M3, A and C; so jobs 1 and 3. Starting time of job 1 on machine 3 should be after
the completion time of job 3 on machine 3, which is t13 is greater than or equal to t33
plus p33 or the other way. Only one of them is valid. Only when both are valid you can
do the addition, etc. Only one of them is eventually valid. We will see how we model
that. If you take machine 2, you get into a much
more different situation because M2 is handling all the three jobs. You have to write three
sets of either or. For example, if you take the pair AB, then either A is ahead of B or
B is ahead of A. If you take the pair BC, then B is ahead of C or C is ahead of A. If
you take the pair AC, either A is ahead of C or C is ahead of A. You will have three
pairs of either or constraints. Since we are doing it first time, we will write down all
the three pairs. For AB you will have t12 is greater than or equal to t22 plus p22 or
t22 is greater than or equal to t12 plus p12, this is for AB. Now for BC, t22 is greater
than or equal to t32 plus p32 and t32 is greater than or equal to t22 plus p22, this is one
pair. For 1 3 you will have t12 is greater than or equal to t32 plus p32 or t32 is greater
than or equal to t12 plus p12, you have another set.
In general, if all the jobs go through all the machines, then you will have Mn pairs
of constraints. How do you model this? This is where the integer programming comes in.
We just look at one of these; we can similarly model the rest of them. If you take one pair,
what you first have to do is to write this in this form.
If you take the first constraint this is written as t11 plus p11 minus t21 less than or equal
to 0, t21 plus p21 minus t11 less than or equal to 0. The first thing you have to do
is to write them as less than or equal to 0. Then you write this as t11 plus p11 minus
t21 less than or equal to M into delta1 and t21 plus p21 minus t11 is less than or equal
to M into 1 minus delta1. Initially let us call it only delta. Let us not give any subscript
to that delta. Later we will do that. This will become M delta and M into 1 minus delta,
where M is the well known M; large, positive and tends to infinity, the big M and delta
is the 0, 1 variable. Now what will happen? If this constraint is binding, that is, if
it is advantageous for you to start 2 after you complete 1 in your final solution, if
this constraint is binding, then this is the one that is binding; this is the one that
is binding, so your delta will take a value 0. If this is binding, delta will take the
value 0 implies this is redundant 1 minus delta is 1. It is a redundant constraint,
less than or equal to M is the redundant constraint. On the other hand if the other one is advantageous
to you, then delta will take the value 1 to make this binding and make this redundant.
For every pair you will introduce the delta. Every either or situation will have two constraints
and a delta which is a 0, 1 variable. You will have to introduce as many deltas as the
number of pairs that you have. To give an identity to this delta you can call this delta,
say delta121 because this represents jobs 1 and 2 on machine 1. For example, this constraint
was written for machine 1 for jobs 1 and 2. You can call this as delta121, this will be
delta121, delta121 as the 0, 1 variable. Similarly, you can name every one of these deltas. This
will become in this case 1 3 3 and this will have the 1 2 2, 2 3 2, 1 3 2. For every pair
you will have a delta.
Suppose for some reason or other if I put a limit on the completion time of each one.
I say that job A has to be over by a certain due date, which is called da. Each has a due
date or something like that and that is a very simple constraint. Completion time of
job A is nothing but t13 plus p13 should be less than or equal to d1. Now I have to minimize
the make span, so I have the three completion time.
For this the completion time will be t13 plus p13. This will be t21 plus p21. This will
be t32 plus p32. These are the completion times of the three jobs A, B and C, respectively.
What do I want to do? I want to minimize the make span, which means I am minimizing the
maximum of the 3 numbers. So I end up writing minimize some v and v is the maximum of all
of them. So what will happen? v is greater than or equal to t13 plus p13, v is greater
than or equal to t21 plus p21, v is greater than or equal to t32 plus p32. You do not
have to necessarily restrict the t�s to integers or p�s to integer; depends on the
whole thing. It is likely that if the processing times are integers, then all the t�s will
also be integers. Right now you do not have to worry about any of them. You will just
say tij, v greater than or equal to 0, deltaijk equal to 0, 1. This is the formulation for
the job shop scheduling problem. What is d1? d1 is called the due date for
each job. Due date is something like a due time before which you have to complete the
job. So if something like a d1 is given to you, then you will add constraints saying
completion time of the job 1 should be before the d1. Completion time of the job 1 is start
time on machine 3 plus processing time on machine 3. So this will be a due date related
constraint.
If I do not want to minimize this make span, instead I say that I give you a due date for
each one of them, d1, d2 and d3. I am not going to force you to say that you have to
complete before d1or d2 or d3. I am going to say I want you to minimise the total delay.
That is a very reasonable objective. In that case you assume that these three jobs actually
go to three different customers and each job has a certain due date given by the customer.
Ideally you would like to meet that due date. If you are not able to meet the due date,
you would at least like to minimise the total delay that is there, from your point of view.
This constraint will not be there. You are not going to be forced to complete within
the due date. Then you need to look at one thing. We have these three different completion
times and you have associated due times with each one. We call them d1, d2 and d3. We have
already written here. Now the delay in scheduling sequencing terminology is called by different
terms. If this completion time is before the due date then this job is called early, it
is completed early. If this is after the due date then the job is called tardy. So a job
can either be early or tardy. The term late is a very generic term. Lateness
is the difference between the due date and the completion time. If the lateness is negative
it means the job is completed early. If the lateness is positive, then the job is behind
and then it is called tardy. Now what do you want to minimize? Right now you do not want
to minimise the earliness. You are interested only in minimizing the tardiness. So what
you have to do is you have to define tardiness for each one of these. What will be your tardiness?
Tardiness will be say d1 minus t13 plus p13 or minus d1; this will be your tardiness.
This is the completion; this is the due date and if this difference is positive, then it
is tardiness. If this difference is negative then tardiness is 0.
The actual tardiness is maximum of 0, t13 plus p13 minus d1, this is the tardiness.
If the job is early, this is negative and then your tardiness is 0. What you have to
do now, is you have to define u1 greater than or equal to 0, u1 greater than or equal t13
plus p13 minus d1. u1 greater than or equal to 0 is anyway a non negativity constraint.
You do not have to explicitly state this into the formulation as a constraint. You will
just define this and similarly u2 is greater than or equal to t21 plus p21 minus d2, your
u3 will be greater than or equal to t32 plus p32 minus d3. You will also have u1 greater
than or equal to 0, u2 greater than or equal to 0, u3 greater than or equal to 0.
Now your objective function will be to minimize u1 plus u2 plus u3. You will get this. So
depending on the objective function formulation becomes different. If you want to minimize
not only the sum of tardiness, but you also want to minimize the sum of earliness as well
as tardiness then you will end up doing minimize sigma modulus say some tij plus pij minus
di. There are certain situations where even earliness is not desirable. What will happen
is, if you finish the job early you would like to send it to your customer. Customer
may not want to receive it, he will say that I have put my schedule in such a way that
this item is going to go to production only tomorrow. It is enough if you send me tomorrow
or tomorrow morning; do not send it today morning or two days earlier. I do not want
to hold that inventory in my possession. Those are issues related with operations; there
are situations. Tardiness is much more undesirable than earliness but there are problems where
this is important. We are only interested in modeling, so you will get something like
this. Difficulty again will be you have to write this explicitly, because this can be
positive or negative and then you have to handle it accordingly. Modulus is not directly
a linear thing, so again you have to convert this modulus into another linear thing.
These are the issues. The understanding, particularly from the job scheduling is this �either
or�and that is the most important thing. The �either or� constraint will keep repeating
again and again in every integer programming formulation, particularly when you are looking
at processes and manufacturing related issues where a job or a processor can handle only
one job at a time. The moment it can handle multiple jobs you do not have to worry so
much, but then if it can handle a maximum of k jobs then you have to put another constraint
y1 plus y2 plus yn less than or equal to k and y will be 0, 1. All these are issues in
formulating examples. There are still one or two more examples that we will look at
in the next lecture.
