你好，
我正在尝试使用纸浆算法来解决作业排序问题。我知道这不是使用MIP求解器来解决作业排序的最佳方法，但是它只是用于培训。
但是我的代码不好，并且不能产生好的解决方案（全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)])))
将timeToFinishPreviousWork约束替换为if，但仍然无法正常工作。我用了这个：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)])))
最后找到了解决方法:)返回：
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)]