P
papachunks
Can anyone help solve the following program model? I'm really not sure
what to do but I do have to use solver.
The N-P hard problem is:
Pm/rj/ ∑WjCjj
A set of n=25 jobs and a set of m=4 machines and processing times Pij
(the processing time of job j on the machine i), i = 1, …,4, j = 1,…,
25; job weights w1,…,w25. Objective: Schedule the jobs on the 4
machines so that ∑wjCj is minimized, where Cj is the completion time
of job j.
The basic idea is to introduce an interval-indexed linear program,
akin to the time indexed linear program of the previous subsection.
Let ï‡o = 1, and let ï‡l =2 l-1 , l = 1,…,L, where L is large enough
that every feasible schedule of interest completes by time 2 L-1 . (By
a slight abuse of notation, we let (ï‡o,ï‡1) = (1,1) indicate the point
interval (1,1)). Let:
Xijl = 1, if Jj is assigned to Mi to complete in interval (ï‡l--1ï‡l)
0, otherwise,
For i = 1,…,4, j = 1,…,25 and l = 1,…,L, let Pij be the processing
time of Jj on Mi, for all i,j. We can then write down the following
linear programming formulation whose objective function gives a lower
bound on the total weighted completion time:
Min ∑ ∑ ∑ ï‡l-1Xijl
Subject to
1) ∑ ∑ Xijl = 1 j = 1,…,25
2) ∑ PijXijl ≤ ï‡l, i = 1,…,4, l = 1,…,L
3) Xijl = 0 if rj√i,j,l + pij > ï‡l , √i,j,l
4) Xijl ≥ 0 √i,j,l
Observe that the machine load constraints (2) are sufficient relaxed
to accommodate the possibility that a job could start a time zero and
yet contribute to the load of interval (ï‡l--1ï‡l) ; thusany
solution vector x corresponding to an integral, feasible schedule is
feasible for this LP. Further observe that if Jj completes in
(ï‡l--1ï‡l) then its contribution to the objective function is wjï‡l—1, a
lower bound on its contribution to the actual schedule.
what to do but I do have to use solver.
The N-P hard problem is:
Pm/rj/ ∑WjCjj
A set of n=25 jobs and a set of m=4 machines and processing times Pij
(the processing time of job j on the machine i), i = 1, …,4, j = 1,…,
25; job weights w1,…,w25. Objective: Schedule the jobs on the 4
machines so that ∑wjCj is minimized, where Cj is the completion time
of job j.
The basic idea is to introduce an interval-indexed linear program,
akin to the time indexed linear program of the previous subsection.
Let ï‡o = 1, and let ï‡l =2 l-1 , l = 1,…,L, where L is large enough
that every feasible schedule of interest completes by time 2 L-1 . (By
a slight abuse of notation, we let (ï‡o,ï‡1) = (1,1) indicate the point
interval (1,1)). Let:
Xijl = 1, if Jj is assigned to Mi to complete in interval (ï‡l--1ï‡l)
0, otherwise,
For i = 1,…,4, j = 1,…,25 and l = 1,…,L, let Pij be the processing
time of Jj on Mi, for all i,j. We can then write down the following
linear programming formulation whose objective function gives a lower
bound on the total weighted completion time:
Min ∑ ∑ ∑ ï‡l-1Xijl
Subject to
1) ∑ ∑ Xijl = 1 j = 1,…,25
2) ∑ PijXijl ≤ ï‡l, i = 1,…,4, l = 1,…,L
3) Xijl = 0 if rj√i,j,l + pij > ï‡l , √i,j,l
4) Xijl ≥ 0 √i,j,l
Observe that the machine load constraints (2) are sufficient relaxed
to accommodate the possibility that a job could start a time zero and
yet contribute to the load of interval (ï‡l--1ï‡l) ; thusany
solution vector x corresponding to an integral, feasible schedule is
feasible for this LP. Further observe that if Jj completes in
(ï‡l--1ï‡l) then its contribution to the objective function is wjï‡l—1, a
lower bound on its contribution to the actual schedule.