单机调度 – 截止日期约束

huangapple go评论135阅读模式
英文:

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

huangapple
  • 本文由 发表于 2023年7月14日 04:15:36
  • 转载请务必保留本文链接:https://go.coder-hub.com/76682960.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定