MIP 的 JOB SEQUENCING 解决方案（使用纸浆）
JOB SEQUENCING resolution with MIP (using pulp)
您好，
我正在尝试用 pulp 创建一个算法来解决 JOB SEQUENCING 问题。我知道这不是使用 MIP 求解器解决 JOB SEQUENCING 的最佳方法，但它仅用于训练。
但是我的代码不好，不能产生好的解决方案（全0）。
所以如果有人帮忙可以看看。谢谢！
import numpy
import pulp
import time
# Work must me achieve before :
deadline=[2,4,3,7,10]
# Score of each work :
score = [10,30,20,50,20]
# Time to do the work :
time=[2,2,2,5,3]
# Just works index :
works = [0,1,2,3,4]
tMax = max(deadline)
nItem = len(deadline)
# Create (item, time) variables
s = [(i,j) for i in range(0,nItem) for j in range(0,tMax)]
prob = pulp.LpProblem("Job_Sequencing_Problem", pulp.LpMaximize)
wk = pulp.LpVariable.dicts("Works", s,lowBound=0, upBound=1, cat=pulp.LpInteger)
# We want to maximize the score
prob+=pulp.lpSum([wk[(i,j)]*score[i] for i in range (0,nItem) for j in range(0,tMax)])
# Respect deadline constraints
for i in range (0,nItem):
for j in range(0,tMax):
# j represent time(or step) where we are
# If we are at t=3 and the object takes 2 sec to compile
# but the deadline is t=4 it's not good
if j>(deadline[i]-time[i]):
prob+=pulp.lpSum(wk[(i,j)])==0
for i in range(0,nItem):
# Works can only be done once
prob+=pulp.lpSum([wk[(i,j)] for j in range(0,tMax)]) <=1
# We must add time to achieve work constraint
for j in range(0,tMax):
# If the sum of time to achive work of before jobs, are greater than the current time who we
# are, it's not good, so we add this constraint
timeToFinishPreviousWork = 0
for x in range(0,tMax-1):
for y in range(0,nItem):
timeToFinishPreviousWork += wk[(y,x)]*time[y]
# wk[(i,j)]*(j+1) = current t
prob+=pulp.lpSum(wk[(i,j)]*(j+1)) >= timeToFinishPreviousWork
prob.solve()
for i in range(0,nItem):
for j in range(0,tMax):
print("%s = %f" % (wk[(i,j)], pulp.value(wk[(i,j)])))
用 if else 更改 timeToFinishPreviousWork 约束，但仍然不起作用。我用过这个：https://math.stackexchange.com/questions/2500415/how-to-write-if-else-statement-in-linear-programming/2501007
我想说的是，如果当前时间比做上一个工作的时间差那么这是不可能的，所以变量等于 0
import numpy
import pulp
import time
# Work must me achieve before :
deadline=[4,4,3,7,10]
# Score of each work :
score = [10,30,20,50,20]
# Time to do the work :
time=[2,2,2,5,3]
# Just worker index :
worker = [0,1,2,3,4]
M=100000
tMax = max(deadline)
nItem = len(deadline)
# Create (item, time) variables
s = [(i,j) for i in range(0,nItem) for j in range(0,tMax)]
prob = pulp.LpProblem("Job_Sequencing_Problem", pulp.LpMaximize)
wk = pulp.LpVariable.dicts("Worker", s,lowBound=0, upBound=1, cat=pulp.LpInteger)
omega = [(i,j) for i in range(0,nItem) for j in range(0,tMax)]
c = pulp.LpVariable.dicts("Omega", s,lowBound=0, upBound=1, cat=pulp.LpInteger)
# We want to maximize the score
prob+=pulp.lpSum([wk[(i,j)]*score[i] for i in range (0,nItem) for j in range(0,tMax)])
# Respect deadline constraints
for i in range (0,nItem):
for j in range(0,tMax):
# j represent time(or step) where we are
# If we are at t=3 and the object takes 2 sec to compilate
# but the deadline is t=4 it's note good
if j>(deadline[i]-time[i]):
prob+=pulp.lpSum(wk[(i,j)])==0
for j in range(0,tMax):
prob+=pulp.lpSum([wk[(i,j)] for i in range (0,nItem)]) <=1
for i in range(0,nItem):
# Works can only be done once
prob+=pulp.lpSum([wk[(i,j)] for j in range(0,tMax)]) <=1
# We must add time to achieve work constraint
for j in range(0,tMax):
# If the sum of time to achive work of before jobs, are greater than the current time who we
# are, it's not good, so we add this constraint
timeToFinishPreviousWork = 0
# j=-1 to count only previous job(not current)
for x in range(0,j-1):
for y in range(0,nItem):
timeToFinishPreviousWork += wk[(y,x)]*time[y]
# wk[(i,j)]*(j+1) = current t
# if timeToFinishPreviousWork > wk[(i,j)]*j(represent current time) then wk[(i,j)]=0
prob+=pulp.lpSum(timeToFinishPreviousWork) >=wk[(i,j)]*(j+1) -M*(1-c[(i,j)])
prob+=pulp.lpSum(timeToFinishPreviousWork) <=wk[(i,j)]*(j+1) +M*(c[(i,j)])
prob+=pulp.lpSum(0-M*(1-c[(i,j)])) <= wk[(i,j)]
prob+=pulp.lpSum(0+M*(1-c[(i,j)])) >= wk[(i,j)]
prob.solve()
for i in range(0,nItem):
for j in range(0,tMax):
print("%s = %d" % (wk[(i,j)], pulp.value(wk[(i,j)])))
终于找到解决办法了:)
Return:
Worker_(2,_0) = 1
Worker_(3,_2) = 1
Worker_(4,_9) = 1
注意：时间j没有最小化，因为它必须用Worker_(4,_7) = 1代替
import numpy
import pulp
import time
# Work must me achieve before :
deadline=[4,4,3,7,13]
# Score of each work :
score = [10,30,60,60,20]
# Time to do the work :
time=[2,2,2,5,3]
# Just worker index :
worker = [0,1,2,3,4]
M=100000
tMax = max(deadline)
nItem = len(deadline)
# Create (item, time) variables
s = [(i,j) for i in range(0,nItem) for j in range(0,tMax)]
prob = pulp.LpProblem("Job_Sequencing_Problem", pulp.LpMaximize)
wk = pulp.LpVariable.dicts("Worker", s,lowBound=0, upBound=1, cat=pulp.LpInteger)
omega = [(i,j) for i in range(0,nItem) for j in range(0,tMax)]
c = pulp.LpVariable.dicts("Omega", s,lowBound=0, upBound=1, cat=pulp.LpInteger)
# We want to maximize the score
prob+=pulp.lpSum([wk[(i,j)]*score[i] for i in range (0,nItem) for j in range(0,tMax)])
# Respect deadline constraints
for i in range (0,nItem):
for j in range(0,tMax):
# j represent time(or step) where we are
# If we are at t=3 and the object takes 2 sec to compilate
# but the deadline is t=4 it's note good
if j>(deadline[i]-time[i]):
prob+=pulp.lpSum(wk[(i,j)])==0
for j in range(0,tMax):
prob+=pulp.lpSum([wk[(i,j)] for i in range (0,nItem)]) <=1
prob+=pulp.lpSum([wk[(i,0)] for i in range(0,nItem)]) ==1
for i in range(0,nItem):
# Works can only be done once
prob+=pulp.lpSum([wk[(i,j)] for j in range(0,tMax)]) <=1
# We must add time to achieve work constraint
for j in range(0,tMax):
# If the sum of time to achive work of before jobs, are greater than the current time who we
# are, it's not good, so we add this constraint
timeToFinishPreviousWork = 0
# j=-1 to count only previous job(not current)
for x in range(0,j):
for y in range(0,nItem):
timeToFinishPreviousWork += wk[(y,x)]*time[y]
# wk[(i,j)]*(j+1) = current t
# if timeToFinishPreviousWork > wk[(i,j)]*j(represent current time) then wk[(i,j)]=0
prob+=pulp.lpSum(timeToFinishPreviousWork) >=wk[(i,j)]*(j) -M*(1-c[(i,j)])
prob+=pulp.lpSum(timeToFinishPreviousWork) <=wk[(i,j)]*(j) +M*(c[(i,j)])
prob+=pulp.lpSum(0-M*(1-c[(i,j)])) <= wk[(i,j)]
prob+=pulp.lpSum(0+M*(1-c[(i,j)])) >= wk[(i,j)]
您好，
我正在尝试用 pulp 创建一个算法来解决 JOB SEQUENCING 问题。我知道这不是使用 MIP 求解器解决 JOB SEQUENCING 的最佳方法，但它仅用于训练。
但是我的代码不好，不能产生好的解决方案（全0）。 所以如果有人帮忙可以看看。谢谢！
import numpy
import pulp
import time
# Work must me achieve before :
deadline=[2,4,3,7,10]
# Score of each work :
score = [10,30,20,50,20]
# Time to do the work :
time=[2,2,2,5,3]
# Just works index :
works = [0,1,2,3,4]
tMax = max(deadline)
nItem = len(deadline)
# Create (item, time) variables
s = [(i,j) for i in range(0,nItem) for j in range(0,tMax)]
prob = pulp.LpProblem("Job_Sequencing_Problem", pulp.LpMaximize)
wk = pulp.LpVariable.dicts("Works", s,lowBound=0, upBound=1, cat=pulp.LpInteger)
# We want to maximize the score
prob+=pulp.lpSum([wk[(i,j)]*score[i] for i in range (0,nItem) for j in range(0,tMax)])
# Respect deadline constraints
for i in range (0,nItem):
for j in range(0,tMax):
# j represent time(or step) where we are
# If we are at t=3 and the object takes 2 sec to compile
# but the deadline is t=4 it's not good
if j>(deadline[i]-time[i]):
prob+=pulp.lpSum(wk[(i,j)])==0
for i in range(0,nItem):
# Works can only be done once
prob+=pulp.lpSum([wk[(i,j)] for j in range(0,tMax)]) <=1
# We must add time to achieve work constraint
for j in range(0,tMax):
# If the sum of time to achive work of before jobs, are greater than the current time who we
# are, it's not good, so we add this constraint
timeToFinishPreviousWork = 0
for x in range(0,tMax-1):
for y in range(0,nItem):
timeToFinishPreviousWork += wk[(y,x)]*time[y]
# wk[(i,j)]*(j+1) = current t
prob+=pulp.lpSum(wk[(i,j)]*(j+1)) >= timeToFinishPreviousWork
prob.solve()
for i in range(0,nItem):
for j in range(0,tMax):
print("%s = %f" % (wk[(i,j)], pulp.value(wk[(i,j)])))
用 if else 更改 timeToFinishPreviousWork 约束，但仍然不起作用。我用过这个：https://math.stackexchange.com/questions/2500415/how-to-write-if-else-statement-in-linear-programming/2501007
我想说的是，如果当前时间比做上一个工作的时间差那么这是不可能的，所以变量等于 0
import numpy
import pulp
import time
# Work must me achieve before :
deadline=[4,4,3,7,10]
# Score of each work :
score = [10,30,20,50,20]
# Time to do the work :
time=[2,2,2,5,3]
# Just worker index :
worker = [0,1,2,3,4]
M=100000
tMax = max(deadline)
nItem = len(deadline)
# Create (item, time) variables
s = [(i,j) for i in range(0,nItem) for j in range(0,tMax)]
prob = pulp.LpProblem("Job_Sequencing_Problem", pulp.LpMaximize)
wk = pulp.LpVariable.dicts("Worker", s,lowBound=0, upBound=1, cat=pulp.LpInteger)
omega = [(i,j) for i in range(0,nItem) for j in range(0,tMax)]
c = pulp.LpVariable.dicts("Omega", s,lowBound=0, upBound=1, cat=pulp.LpInteger)
# We want to maximize the score
prob+=pulp.lpSum([wk[(i,j)]*score[i] for i in range (0,nItem) for j in range(0,tMax)])
# Respect deadline constraints
for i in range (0,nItem):
for j in range(0,tMax):
# j represent time(or step) where we are
# If we are at t=3 and the object takes 2 sec to compilate
# but the deadline is t=4 it's note good
if j>(deadline[i]-time[i]):
prob+=pulp.lpSum(wk[(i,j)])==0
for j in range(0,tMax):
prob+=pulp.lpSum([wk[(i,j)] for i in range (0,nItem)]) <=1
for i in range(0,nItem):
# Works can only be done once
prob+=pulp.lpSum([wk[(i,j)] for j in range(0,tMax)]) <=1
# We must add time to achieve work constraint
for j in range(0,tMax):
# If the sum of time to achive work of before jobs, are greater than the current time who we
# are, it's not good, so we add this constraint
timeToFinishPreviousWork = 0
# j=-1 to count only previous job(not current)
for x in range(0,j-1):
for y in range(0,nItem):
timeToFinishPreviousWork += wk[(y,x)]*time[y]
# wk[(i,j)]*(j+1) = current t
# if timeToFinishPreviousWork > wk[(i,j)]*j(represent current time) then wk[(i,j)]=0
prob+=pulp.lpSum(timeToFinishPreviousWork) >=wk[(i,j)]*(j+1) -M*(1-c[(i,j)])
prob+=pulp.lpSum(timeToFinishPreviousWork) <=wk[(i,j)]*(j+1) +M*(c[(i,j)])
prob+=pulp.lpSum(0-M*(1-c[(i,j)])) <= wk[(i,j)]
prob+=pulp.lpSum(0+M*(1-c[(i,j)])) >= wk[(i,j)]
prob.solve()
for i in range(0,nItem):
for j in range(0,tMax):
print("%s = %d" % (wk[(i,j)], pulp.value(wk[(i,j)])))
终于找到解决办法了:) Return:
Worker_(2,_0) = 1
Worker_(3,_2) = 1
Worker_(4,_9) = 1
注意：时间j没有最小化，因为它必须用Worker_(4,_7) = 1代替
import numpy
import pulp
import time
# Work must me achieve before :
deadline=[4,4,3,7,13]
# Score of each work :
score = [10,30,60,60,20]
# Time to do the work :
time=[2,2,2,5,3]
# Just worker index :
worker = [0,1,2,3,4]
M=100000
tMax = max(deadline)
nItem = len(deadline)
# Create (item, time) variables
s = [(i,j) for i in range(0,nItem) for j in range(0,tMax)]
prob = pulp.LpProblem("Job_Sequencing_Problem", pulp.LpMaximize)
wk = pulp.LpVariable.dicts("Worker", s,lowBound=0, upBound=1, cat=pulp.LpInteger)
omega = [(i,j) for i in range(0,nItem) for j in range(0,tMax)]
c = pulp.LpVariable.dicts("Omega", s,lowBound=0, upBound=1, cat=pulp.LpInteger)
# We want to maximize the score
prob+=pulp.lpSum([wk[(i,j)]*score[i] for i in range (0,nItem) for j in range(0,tMax)])
# Respect deadline constraints
for i in range (0,nItem):
for j in range(0,tMax):
# j represent time(or step) where we are
# If we are at t=3 and the object takes 2 sec to compilate
# but the deadline is t=4 it's note good
if j>(deadline[i]-time[i]):
prob+=pulp.lpSum(wk[(i,j)])==0
for j in range(0,tMax):
prob+=pulp.lpSum([wk[(i,j)] for i in range (0,nItem)]) <=1
prob+=pulp.lpSum([wk[(i,0)] for i in range(0,nItem)]) ==1
for i in range(0,nItem):
# Works can only be done once
prob+=pulp.lpSum([wk[(i,j)] for j in range(0,tMax)]) <=1
# We must add time to achieve work constraint
for j in range(0,tMax):
# If the sum of time to achive work of before jobs, are greater than the current time who we
# are, it's not good, so we add this constraint
timeToFinishPreviousWork = 0
# j=-1 to count only previous job(not current)
for x in range(0,j):
for y in range(0,nItem):
timeToFinishPreviousWork += wk[(y,x)]*time[y]
# wk[(i,j)]*(j+1) = current t
# if timeToFinishPreviousWork > wk[(i,j)]*j(represent current time) then wk[(i,j)]=0
prob+=pulp.lpSum(timeToFinishPreviousWork) >=wk[(i,j)]*(j) -M*(1-c[(i,j)])
prob+=pulp.lpSum(timeToFinishPreviousWork) <=wk[(i,j)]*(j) +M*(c[(i,j)])
prob+=pulp.lpSum(0-M*(1-c[(i,j)])) <= wk[(i,j)]
prob+=pulp.lpSum(0+M*(1-c[(i,j)])) >= wk[(i,j)]