python - Ortools - Jobshop - 根据他们在机器上的排名修改任务持续时间
问题描述
我正在处理作业车间问题的一个变体,我希望根据他们在机器计划中的分配/排名来修改任务持续时间。
例如,一个简单的情况是,分配到机器上的第一个任务将花费 50% 的时间来完成。
更一般的情况是机器上的每第 n 个任务都需要 X% 的时间。
我已经阅读了有关通道约束的信息,但我不确定如何在这种情况下实现它们,或者是否有其他更好的选择。任何方向将不胜感激。
以下是我使用的代码或工具文档来解决作业车间问题。
from __future__ import print_function
import collections
# Import Python wrapper for or-tools CP-SAT solver.
from ortools.sat.python import cp_model
def MinimalJobshopSat():
"""Minimal jobshop problem."""
# Create the model.
model = cp_model.CpModel()
jobs_data = [ # task = (machine_id, processing_time).
[(2, 1), (0, 1), (1, 1)], # Job0
[(0, 1), (1, 1)], # Job1
[(1, 1), (2, 1)] # Job2
]
machines_count = 1 + max(task[0] for job in jobs_data for task in job)
all_machines = range(machines_count)
# Computes horizon dynamically as the sum of all durations.
horizon = sum(task[1] for job in jobs_data for task in job)
# Named tuple to store information about created variables.
task_type = collections.namedtuple('task_type', 'start end interval')
# Named tuple to manipulate solution information.
assigned_task_type = collections.namedtuple('assigned_task_type',
'start job index duration')
# Creates job intervals and add to the corresponding machine lists.
all_tasks = {}
machine_to_intervals = collections.defaultdict(list)
for job_id, job in enumerate(jobs_data):
for task_id, task in enumerate(job):
machine = task[0]
duration = task[1]
suffix = '_%i_%i' % (job_id, task_id)
start_var = model.NewIntVar(0, horizon, 'start' + suffix)
end_var = model.NewIntVar(0, horizon, 'end' + suffix)
interval_var = model.NewIntervalVar(start_var, duration, end_var,
'interval' + suffix)
all_tasks[job_id, task_id] = task_type(
start=start_var, end=end_var, interval=interval_var)
machine_to_intervals[machine].append(interval_var)
# Create and add disjunctive constraints.
for machine in all_machines:
model.AddNoOverlap(machine_to_intervals[machine])
# # Precedences inside a job.
# Change constraint to only respect the project start date i.e. the first dummy task
for job_id, job in enumerate(jobs_data):
for task_id in range(len(job) - 1):
model.Add(all_tasks[job_id, task_id + 1].start >= all_tasks[job_id, task_id].end)
对于这种情况,我们期望的修改输出如下,其中每台机器上第一个任务的持续时间增加了 50%
Optimal Schedule Length: 4
Machine 0: job_1_0 job_0_1
[0,2] [2,3]
Machine 1: job_2_0 job_0_2 job_1_1
[0,2] [2,3] [3,4]
Machine 2: job_0_0 job_2_1
[0,2] [2,3]
解决方案
推荐阅读
- c - 结构定义缺失“()”的宏 - QAC 错误
- java - 无法解决的构建扩展:插件 org.apache.maven.wagon:wagon-webdav-jackrabbit:1.0-beta-6
- automapper - Automapper 8 - 表达式树 lambda 可能不包含空传播运算符
- php - Symfony 4.2 无法连接到 Microsoft SQL Server
- c - 如何解决堆栈损坏错误?
- anaconda - 运行 jupyter notebook 后连接被拒绝(503 错误)
- python - 从PDF读取并存储在数据框中时如何保留表结构?
- jquery - jQuery 函数不是函数 - 如何?
- stripe-payments - Gravity Form Stripe 试用 + 安装费
- symfony - Homestead 没有加载页面(symfony)