排序论又称为时间表理论,是一类重要的组合优化问题。随着社会的发展, 新的模型层出不穷,并且绝大多数是NP-难问题或强NP-难问题。动态规划是求 解组合最优化问题的一个重要方法,特别适合求解NP-难问题,在工程技术、经 济管理、工业生产和军事等方面都有着广泛的应用。在排序问题越来越复杂的 情况下,只要运用得当,动态规划这个传统的方法可以成为解决复杂问题的较 好途径。 本文讨论排序问题的动态规划算法,考虑的排序模型涉及供应链排序、工 件加工时间可控排序、工件可拒绝排序,以及工件有优先约束的排序问题。 第一章介绍了用动态规划方法解决问题的基本步骤,总结了用动态规划方 法设计排序问题算法的基本情况,其中涉及的排序问题类型有经典的单机、平 行机问题,可中断排序问题,车间作业问题,柔性流水作业问题,同时加工问 题,成组排序问题,以及供应链问题。 第二章和第三章是本文的主要内容。主要研究以下几个问题： 1.供应链排序问题 (1)在只有一个供应商的树状供应链中,研究平行机加工工件,使排序费用和 发送费用达到最小的问题。对用总流程时间衡量排序费用的问题1→G,Pm‖∑Fj +∑Dgyg,证明其强NP-难性,设计最坏性能比是2-1/m的动态规划算法。另外, 证明了问题1→G,Pm‖Lmax+∑Dgyg和1→G,Pmll∑Uj+∑Dgygg的NP-难性质。 (2)在多供应商、多制造商的网状供应链中,分别从供应商和制造商的角度研 究生产的安排和发送的决策问题。用动态规划的方法给出了以下六个问题的最 优算法：供应商阶段的总流程时间问题K－>G,1‖∑Fj+∑Dk,gyk,g,最大延迟问 题K－>G,1‖Lmax+∑Dk,gyk,g和误工工件数问题K－>G,1‖∑Uj+∑Dk,gyk,g,制 造商阶段的总流程时间问题G－>C,1|rj|∑Fj+∑Dg,hyg,h,最大延迟问题G－>C, 1|rj|Lmax+∑Dg,hyg,h和误工工件数问题G－>C,1‖∑Uj+∑Dg,hyg,h。 2．工件加工时间可控排序问题 研究工件具有离散型可控加工时间,安排n个工件使排序费用和控制费用 的总和为最小的加工时间可控的同时加工排序问题。选取不同的排序费用,共 解决了三个问题： 用动态规划的方法为问题1|B,dis_cpt|∑UJ+n∑i=1∑h∑k=1ckIk(xi),1|B,dis_cpt| Lmax+n∑i=1∑h∑k=1ckIk(xi)和1|B,dis_cpt|Cmax+n∑i=1∑h∑k=1ckIk(xi)设计了最优算法。 3．工件可拒绝排序问题 研究安排n个工件,使接受加工工件的带权总完工时间∑j∈SwjCj和拒绝费用 ∑j∈Sej的总和为最小的可拒绝排序问题1|rej|∑j∈Sej+∑j∈SwjCj,给出动态规划求解方 法。对工件可以同时加工的可拒绝排序问题问题1|rej,B|∑j∈Sej+Cmax,也给出动 态规划最优算法。 4．工件有优先约束排序问题 对有先后约束的单台机器排序问题1|prec|∑fj的算法进行修正。 关键词：排序,动态规划,供应链,工件可拒绝,加工时间可控,计算复杂性