动态规划的应用 -排序问题 管理学院管理科学与工程张莹
动态规划的应用 ——排 序 问 题 管理学院 管理科学与工程 张莹
排序问题 ●排序问题指n种零件经过不同设备加工时 的顺序问题。其目的是使加工周期为最短 ●分类: 单台机器的排序问题单件作业(Job-op)排序问题: 工件的加工路线不同 多台机器的排序问题 流水作业(Fow-shop)排序问题: 所有工件的加工路线完全相同
排序问题 ⚫排序问题指n 种零件经过不同设备加工时 的顺序问题。其目的是使加工周期为最短。 ⚫分类： 单台机器的排序问题 多台机器的排序问题 单件作业（Job-shop）排序问题： 工件的加工路线不同 流水作业（Flow-shop）排序问题： 所有工件的加工路线完全相同
n×2排序问题 即n种零件经过2种设备进行加工,如何 安排? 设有n个工件需要在机床A、B上加工,每 工件都必须先经过A而后B两道加工工序 以ai、bi分别表示工件(1sn)在A、B上的 加工时间。问应如何在两机床上安排各工 件的加工顺序,使在机床A上加工第一个工 件开始到在机床B上加工完最后一个工件为 止,所用的加工总时间最少?
n × 2 排序问题 ⚫ 即n 种零件经过2 种设备进行加工，如何 安排？ 设有n个工件需要在机床A、B上加工，每个 工件都必须先经过A而后B•两道加工工序。 以ai、bi分别表示工件i(1≤i≤n)在A、B上的 加工时间。问应如何在两机床上安排各工 件的加工顺序，使在机床A上加工第一个工 件开始到在机床B上加工完最后一个工件为 止，所用的加工总时间最少？
分析: 加工工件在机床A上有加工顺序问题,在机 床B上也有加工顺序问题。可以证明:最优 排序方案可以只在机床A、B上加工顺 序相同的排序中寻找。即使如此,所有 可能的方案仍有n!个,这是一个不小的数, 用穷举法是不现实的
分析： 加工工件在机床A上有加工顺序问题，在机 床B上也有加工顺序问题。可以证明：最优 排序方案可以只在机床A、B上加工顺 序相同的排序中寻找。即使如此，所有 可能的方案仍有n!个，这是一个不小的数， 用穷举法是不现实的
问题: 如何用动态规划方法来研究同 顺序两台机床加工N个工件的 排序问题?
问题： 如何用动态规划方法来研究同 顺序两台机床加工N个工件的 排序问题？