英文:
Single machine scheduling - due dates constraints
问题
我正在尝试使用Python的pulp库编写单机调度/瓶颈优化程序,但不想使用for循环以更好地理解。我有两个任务,分别称为task1和task2,它们的持续时间分别为1小时和3小时,截止日期分别为1小时和4小时。
以下是两种解决方案案例:第一种是不好的,第二种是好的。
# 不好,因为任务1的截止日期已过期
# 小时 1 2 3 4
# task1 -
# task2 - - -
# 好,因为截止日期得到了尊重
# 小时 1 2 3 4
# task1 -
# task2 - - -
我希望pulp求解器能够找到上述第二种解决方案。
以下是我的Pulp代码,解决方案已经接近,也许你可以帮我编写“截止日期”类型的约束,我不知道该怎么做。没有使用FOR循环,这是故意的,以尝试理解...
import pulp as p
# 任务
tasks = ["task1", "task2"]
duration = {1, 3}
due = {1, 4}
starts = {1, 2, 3, 4}
# 创建问题
prob = p.LpProblem('single_machine_scheduling', p.LpMinimize)
# 为任务创建二进制变量
task1_1 = p.LpVariable("task1_1", 0, None, p.LpBinary)
task1_2 = p.LpVariable("task1_2", 0, None, p.LpBinary)
task1_3 = p.LpVariable("task1_3", 0, None, p.LpBinary)
task1_4 = p.LpVariable("task1_4", 0, None, p.LpBinary)
task2_1 = p.LpVariable("task2_1", 0, None, p.LpBinary)
task2_2 = p.LpVariable("task2_2", 0, None, p.LpBinary)
task2_3 = p.LpVariable("task2_3", 0, None, p.LpBinary)
task2_4 = p.LpVariable("task2_4", 0, None, p.LpBinary)
# 用于截止日期约束的变量
start_1 = p.LpVariable("start_1", 0, None, p.LpContinuous)
start_2 = p.LpVariable("start_2", 0, None, p.LpContinuous)
start_3 = p.LpVariable("start_3", 0, None, p.LpContinuous)
start_4 = p.LpVariable("start_4", 0, None, p.LpContinuous)
# 目标:最小化时间跨度
prob += 1 * task1_1 + 1 * task1_2 + 1 * task1_3 + 1 * task1_4 + 3 * task2_1 + 3 * task2_2 + 3 * task2_3 + 3 * task2_4
# 约束条件
# 只能选择一个task1和一个task2
prob += task1_1 + task1_2 + task1_3 + task1_4 == 1
prob += task2_1 + task2_2 + task2_3 + task2_4 == 1
# 截止日期约束(如何实现?)
# 求解
prob.solve()
# 打印变量
for v in prob.variables():
print(v.name, "=", v.varValue)
# 打印目标值
print("最小化时间跨度 =", p.value(prob.objective))
也许你可以指导我正确的方向?我也无法将它们写入数学模型中,我找到的模型包括额外的参数,但我不希望在这里使用它们。
编辑:哎呀,对不起,我已经学到它被称为“总滞后最小化”,以及Moore和Hodgson算法。
英文:
I am trying to program the single machine scheduling/bottleneck optimization, with python pulp, without making for loops to better understand.
I have 2 tasks called task1 and task2 to schedule that respectively last 1H and 3H, with due dates respectively at 1H and 4H.
Here are two solutions cases: first one is bad, the second one is good.
# Ko, because the task 1 due date is outdated
# hours 1 2 3 4
# task1 -
# task2 - - -
# Ok, because due dates are respected
# hours 1 2 3 4
# task1 -
# task2 - - -
I want the pulp solver to find solution 2 above.
Here is my Pulp code, solution is close, maybe you can help me write the "due dates" type constraints, I can't do it.There are no FOR loops, it's done on purpose to try to understand...
import pulp as p
# Tasks
tasks = ["task1","task2"]
duration = {1,3}
due = {1,4}
starts = {1,2,3,4}
# Create problem
prob = p.LpProblem('single_machine_scheduling', p.LpMinimize)
# Each possible "time slots" to select for tasks
task1_1 = p.LpVariable("task1_1", 0, None, p.LpBinary)
task1_2 = p.LpVariable("task1_2", 0, None, p.LpBinary)
task1_3 = p.LpVariable("task1_3", 0, None, p.LpBinary)
task1_4 = p.LpVariable("task1_4", 0, None, p.LpBinary)
task2_1 = p.LpVariable("task2_1", 0, None, p.LpBinary)
task2_2 = p.LpVariable("task2_2", 0, None, p.LpBinary)
task2_3 = p.LpVariable("task2_3", 0, None, p.LpBinary)
task2_4 = p.LpVariable("task2_4", 0, None, p.LpBinary)
# Theses constraints should be used for due dates constraints eventually...
start_1 = p.LpVariable("start_1", 0, None, p.LpContinuous)
start_2 = p.LpVariable("start_2", 0, None, p.LpContinuous)
start_3 = p.LpVariable("start_3", 0, None, p.LpContinuous)
start_4 = p.LpVariable("start_4", 0, None, p.LpContinuous)
# Objective : Minimize timespan
prob += 1 * task1_1 + 1 * task1_2 + 1 * task1_3 + 1 * task1_4 + 3 * task2_1 + 3 * task2_2 + 3 * task2_3 + 3 * task2_4
# Constraints
# Only one task1 and one task2 can be selected
prob += task1_1 + task1_2 + task1_3 + task1_4 == 1
prob += task2_1 + task2_2 + task2_3 + task2_4 == 1
# Due dates constraints ( How to ?)
# Solve
prob.solve()
# Print variables
for v in prob.variables():
print(v.name, "=", v.varValue)
# Print objective
print("Minimized timespan = ", p.value(prob.objective))
start_3 = 0.0
start_4 = 0.0
task1_1 = 0.0
task1_2 = 0.0
task1_3 = 0.0
task1_4 = 1.0
task2_1 = 0.0
task2_2 = 0.0
task2_3 = 0.0
task2_4 = 1.0
Minimized timespan = 4.0
Maybe you can point me in the right direction? I also can't write them in the mathematical model, The ones I found include additional parameters like weight, but I don't want that here..
Edit: Oops sorry, I have learned that it's called "Total Tardiness minimization", and the Moore and Hodgson algorithm .
答案1
得分: 0
这只是一个简单的代码示例,用来说明在pulp
中没有需要优化的问题。一对简单的循环提供了最直接的解决方案:
import itertools
tasks = [("task1", 1, 1), ("task2", 3, 4)]
# 对于每个排列
for tasklist in itertools.permutations(tasks):
time = 1
start = []
order = []
for task in tasklist:
start.append(time)
order.append(task)
time += task[1]
if time - 1 > task[2]:
# 我们违反了截止日期的约束。
break
else:
print("Order", order, "成功")
输出:
Order [('task1', 1, 1), ('task2', 3, 4)] 成功
英文:
I just don't think this is a problem for pulp
, because there's nothing to optimize. A simple pair of loops provides the most straightforward solution:
import itertools
tasks = [("task1", 1, 1), ("task2", 3, 4)]
# For each permutation
for tasklist in itertools.permutations(tasks):
time = 1
start = []
order = []
for task in tasklist:
start.append( time )
order.append( task )
time += task[1]
if time-1 > task[2]:
# We violated a due date constraint.
break
else:
print("Order",order,"succeeds")
Output:
Order [('task1', 1, 1), ('task2', 3, 4)] succeeds
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论