知识卡片
作业车间约束定义可行解
作业车间调度(JSP)要为 n 个工件在 m 台机器上分配共享资源并安排生产任务。候选方案先要满足约束才谈得上优化:
- 同一工件的工序必须按规定次序加工,且每道工序对应不同机器。
- 任意一台机器同一时刻只加工一道工序。
- 加工过程不能插入新工序,也不能临时中断。
- 开工时间非负;各工序加工时间预先给定且不变。
换工艺或允许抢占时,这些约束也要改。
补充教学示例(非书中数据)。工件 J1:机器 1(2)→机器 2(3);工件 J2:机器 2(1)→机器 1(4)。两工件同时占用机器 1,或 J1 先做机器 2,都不可行。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 0 . 4 . 3 基 于 差 分 进 化 算 法 的 作 业 车 间 调 度 · 查看原书依据
(1)对于同一个工件,加工次序必须严格按照顺序进行,且每一道工序对应不同的机器。 (2)任意一台机器一次只能加工一个工件的某一道工序。 (3)机器在运作时不能插入新的工序,也不能临时中断。 (4)每一台机器开始加工的时间一定大于或等于零。
参考来源
- 位置:《智能算法导论》第10章《1 0 . 4 . 3 基 于 差 分 进 化 算 法 的 作 业 车 间 调 度》(源文件:`_epub-src/EPUB/xhtml/chapter10_0013.xhtml`)
- 结论依据:正文依次列出工序次序、机器单工序占用、不可中断、非负开工和固定工时,共同界定可行调度。两工件示意为依据这些约束补充的教学示例,非书中数据。
- 原始内容:(1)对于同一个工件,加工次序必须严格按照顺序进行,且每一道工序对应不同的机器。 (2)任意一台机器一次只能加工一个工件的某一道工序。 (3)机器在运作时不能插入新的工序,也不能临时中断。