Help on solving the linear programming model using solver
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 rji,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) ; thus any
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ďl1, a
lower bound on its contribution to the actual schedule.
|