Help on solving the linear programming model using solver

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top