View Single Post
  #1   Report Post  
Posted to microsoft.public.excel.programming
papachunks papachunks is offline
external usenet poster
 
Posts: 1
Default 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 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) ; 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l€”1, a
lower bound on its contribution to the actual schedule.