单机调度 – 截止日期约束

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

Single machine scheduling - due dates constraints

问题

我正在尝试使用Python的pulp库编写单机调度/瓶颈优化程序，但不想使用for循环以更好地理解。我有两个任务，分别称为task1和task2，它们的持续时间分别为1小时和3小时，截止日期分别为1小时和4小时。

以下是两种解决方案案例：第一种是不好的，第二种是好的。

  1. # 不好，因为任务1的截止日期已过期
  2. # 小时    1 2 3 4
  3. # task1         -
  4. # task2   - - - 
  6. # 好，因为截止日期得到了尊重
  7. # 小时    1 2 3 4
  8. # task1   - 
  9. # task2     - - -

我希望pulp求解器能够找到上述第二种解决方案。

以下是我的Pulp代码，解决方案已经接近，也许你可以帮我编写“截止日期”类型的约束，我不知道该怎么做。没有使用FOR循环，这是故意的，以尝试理解...

  1. import pulp as p
  3. # 任务
  4. tasks = ["task1", "task2"]
  5. duration = {1, 3}
  6. due = {1, 4}
  7. starts = {1, 2, 3, 4}
  9. # 创建问题
  10. prob = p.LpProblem('single_machine_scheduling', p.LpMinimize)  
  12. # 为任务创建二进制变量
  13. task1_1 = p.LpVariable("task1_1", 0, None, p.LpBinary) 
  14. task1_2 = p.LpVariable("task1_2", 0, None, p.LpBinary) 
  15. task1_3 = p.LpVariable("task1_3", 0, None, p.LpBinary) 
  16. task1_4 = p.LpVariable("task1_4", 0, None, p.LpBinary) 
  17. task2_1 = p.LpVariable("task2_1", 0, None, p.LpBinary) 
  18. task2_2 = p.LpVariable("task2_2", 0, None, p.LpBinary) 
  19. task2_3 = p.LpVariable("task2_3", 0, None, p.LpBinary)  
  20. task2_4 = p.LpVariable("task2_4", 0, None, p.LpBinary) 
  22. # 用于截止日期约束的变量
  23. start_1 = p.LpVariable("start_1", 0, None, p.LpContinuous) 
  24. start_2 = p.LpVariable("start_2", 0, None, p.LpContinuous) 
  25. start_3 = p.LpVariable("start_3", 0, None, p.LpContinuous) 
  26. start_4 = p.LpVariable("start_4", 0, None, p.LpContinuous) 
  28. # 目标：最小化时间跨度
  29. 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
  31. # 约束条件
  33. # 只能选择一个task1和一个task2
  34. prob +=  task1_1 + task1_2 + task1_3 + task1_4 == 1
  35. prob +=  task2_1 + task2_2 + task2_3 + task2_4 == 1
  37. # 截止日期约束（如何实现？）
  39. # 求解
  40. prob.solve()
  42. # 打印变量
  43. for v in prob.variables():
  44.     print(v.name, "=", v.varValue)
  46. # 打印目标值
  47. 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.

  1. # Ko, because the task 1 due date is outdated  
  2. # hours   1 2 3 4 
  3. # task1         -
  4. # task2   - - - 
  5. # Ok, because due dates are respected
  6. # hours   1 2 3 4 
  7. # task1   - 
  8. # 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...

  1. import pulp as p
  2. # Tasks
  3. tasks = ["task1","task2"]
  4. duration = {1,3}
  5. due = {1,4}
  6. starts = {1,2,3,4}
  7. # Create problem
  8. prob = p.LpProblem('single_machine_scheduling', p.LpMinimize)  
  9. # Each possible "time slots" to select for tasks
  10. task1_1 = p.LpVariable("task1_1", 0, None, p.LpBinary) 
  11. task1_2 = p.LpVariable("task1_2", 0, None, p.LpBinary) 
  12. task1_3 = p.LpVariable("task1_3", 0, None, p.LpBinary) 
  13. task1_4 = p.LpVariable("task1_4", 0, None, p.LpBinary) 
  14. task2_1 = p.LpVariable("task2_1", 0, None, p.LpBinary) 
  15. task2_2 = p.LpVariable("task2_2", 0, None, p.LpBinary) 
  16. task2_3 = p.LpVariable("task2_3", 0, None, p.LpBinary)  
  17. task2_4 = p.LpVariable("task2_4", 0, None, p.LpBinary) 
  18. # Theses constraints should be used for due dates constraints eventually...
  19. start_1 = p.LpVariable("start_1", 0, None, p.LpContinuous) 
  20. start_2 = p.LpVariable("start_2", 0, None, p.LpContinuous) 
  21. start_3 = p.LpVariable("start_3", 0, None, p.LpContinuous) 
  22. start_4 = p.LpVariable("start_4", 0, None, p.LpContinuous) 
  23. # Objective : Minimize timespan
  24. 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
  25. # Constraints
  26. # Only one task1 and one task2 can be selected
  27. prob +=  task1_1 + task1_2 + task1_3 + task1_4 == 1
  28. prob +=  task2_1 + task2_2 + task2_3 + task2_4 == 1
  29. # Due dates constraints ( How to ?)
  30. # Solve
  31. prob.solve()
  32. # Print variables
  33. for v in prob.variables():
  34. print(v.name, "=", v.varValue)
  35. # Print objective
  36. print("Minimized timespan = ", p.value(prob.objective))
  37. start_3 = 0.0
  38. start_4 = 0.0
  39. task1_1 = 0.0
  40. task1_2 = 0.0
  41. task1_3 = 0.0
  42. task1_4 = 1.0
  43. task2_1 = 0.0
  44. task2_2 = 0.0
  45. task2_3 = 0.0
  46. task2_4 = 1.0
  47. 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中没有需要优化的问题。一对简单的循环提供了最直接的解决方案：

  1. import itertools
  3. tasks = [("task1", 1, 1), ("task2", 3, 4)]
  5. # 对于每个排列
  6. for tasklist in itertools.permutations(tasks):
  7.     time = 1
  8.     start = []
  9.     order = []
  10.     for task in tasklist:
  11.         start.append(time)
  12.         order.append(task)
  13.         time += task[1]
  14.         if time - 1 > task[2]:
  15.             # 我们违反了截止日期的约束。
  16.             break
  17.     else:
  18.         print("Order", order, "成功")

输出：

  1. 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:

  1. import itertools
  2. tasks = [("task1", 1, 1), ("task2", 3, 4)]
  3. # For each permutation
  4. for tasklist in itertools.permutations(tasks):
  5. time = 1
  6. start = []
  7. order = []
  8. for task in tasklist:
  9. start.append( time )
  10. order.append( task )
  11. time += task[1]
  12. if time-1 > task[2]:
  13. # We violated a due date constraint.
  14. break
  15. else:
  16. print("Order",order,"succeeds")

Output:

  1. Order [('task1', 1, 1), ('task2', 3, 4)] succeeds

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

发表评论

匿名网友

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

确定