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.

you'd better use AMPL(mathematical modelling langauge) than excel.

plz visit www.ampl.org
--
msn
---------------------------------------------
the best time to plant a tree was twenty years ago.
the second best time, is today - Chinese proverb



"papachunks" wrote:

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.

sorry not .org

plz refer to www.ampl.com
--
msn
---------------------------------------------
the best time to plant a tree was twenty years ago.
the second best time, is today - Chinese proverb



"papachunks" wrote:

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.