Question

Exercise 10.10 (Job shop scheduling) A factory consists of m machines M1, , Mm, and needs to process n jobs every day. Job j needs to be processed once by each machine in the order (M,a)M(m)). Machine M takes time Pij to process job j. A machine can only process one job at a time, and once a job is started on any machine, it must be processed to complet is to minimize the sum of the completion times of all the jobs. Provide an integer programming formulation for this problem The objective

Answer 1

10.10) Answer: ---- Date: ----23/04/2019

We construct a mixed integer program (MIP). We assume quite a lot is known about our system. Namely, we assume that we know all the job process times on all the machines pij Moreover, for every machine Me we assune that we kuow a value such that Mk-M() for every job i. This just means that for all jobs we know the order of machines on which the job has to be processed, and that we can go backwards from this. So given a machine Mk, we know the order of every job that must be processed on this machine. Let a be the starting time of job i on machine Mtcj), thus aij represents the jth processing step for the total job i. The coustraint that a job i has to be processed first by MiI), then Mi(2) and so on can be modeled by aij tPS a) Vjobs i and j e [1,...,m) where pi(j), is the processing time for job i at the jth processing step, on machine Mu This inequality tells us that the start time for the jth step of job i plus the processing time of that step must be less than the starting time for the (j1)th step, which means jobs are all processed sequentially Or other constraint is a disjunctive one, which says that no machine can proccss more than one job at a time, and this is where we make use of the f that we identified earlier. Let us fix a job i and a machine Mk. For any other job J, we need either aï +pki aj,s, or aj +pkj ai,of This means that machine Mk either processes job i's th task to completion first, or does job j's first. Note that if we fix machine Mk and then range this over all different jobs i and j, this gives us a total ordering for the jobs processed by Mk. Then if we range this over all machines K, this will give us a some ordering for all jobs on all machines. More succinctly, if we keep this XOR condition for every job, then it follows that no machine will every be processing more than one job at a time, and all jobs get processed to completion on all machines In order to model this disjunctive constraint, we employ the tactics of problem (1) in this problem set, by finding some f such that aiat-aik > f for all i jobs. Let C-Σί.jpij which is the sum over all processing times on all machines. Then C serves as a "bound" on how bad our processing time is, if we only processed one job on one machine at a time. So aj^ for all i f j jobs. Thus we introduce binary variables vij such that

where y j-1 means that for machine Mk that job 1 gets processed before job j, and yl, means the opposite. Moreover, we must add the constraint that 3 1- for any machine Mk, since if Mk processes i before j then it cannot also process j before i. Lastly, in our formulation of our problem, the total time spent processing is maxij atj +P)i the maximum of the start times for all jobs i and tasks i(i) plus the processing time for that -0

task for that job. So our MIP is minimize max aij +Pu) subject to ay +Pu)i S a+1) V jobs i and j e fi,...,m) al,st _ aj,s; Pkit (1-%) (-C-pki) vjobs i j and all machines Mk 4,寸-4,2+2 pkj + (-C-pkj) vjobs iメ, and all machines Mk Us-1- ν jobs iメJ and all machines Mk aij 20 Vjobs i and j e f1,... ,m) E 10,1) jobs i A j and all machines M