第1章动态规划基础 1.1多阶段决策过程 1.2动态规划的基本思想 1.3动态规划基础知识 1.3.1基本概念和常用术语 1.3.2动态规划基本模型及基本原理 1.3.3可用动态规划求解的问题的特征 1.4动态规划在组合优化问题中的应用 1.4.1资源分配问题 1.4.2背包问题 1.4.3设备更新问题 第2章排序问题基本理论 2.1排序的记号与术语 2.2算法和复杂性 2.3局部置换法 2.3.1加权完工时间问题 2.3.2*大延迟问题 2.3.3带有到达时间的情形 2.3.4总误工时间问题 第3章单机排序问题 3.1单台机器排序问题1‖∑fj(Cj) 3.1.1问题1‖∑Tj的动态规划算法 3.1.2问题1|dj=d|∑wjTj的动态规划算法 3.1.3工件有先后约束的单台机器排序问题1|prec|∑fj 3.1.4加工允许中断的单台机器排序问题1|pmtn,rj|∑wjUj 3.2单台机器排序问题1‖fmax 3.2.1单台机器排序问题1‖fmax的逆向解法 3.2.2单台机器排序问题1‖fmax的顺向解法 3.2.3工件有先后约束的单台机器排序问题1|prec|fmax 第4章几类新型排序问题 4.1分批排序问题 4.1.1加权总完工时间问题1|p-batch,b=∞|∑wjCj 4.1.2*大延迟问题1|p-batch,b=∞|Lmax 4.2成组排序问题 4.2.1必须满足成组技术要求的成组误工问题1|sf,GT|∑Ui 4.2.2不受成组技术限制的成组排序问题 4.3加工时间可控的排序问题 4.3.1误工工件数问题1|B,dis_cpt|∑Uj ∑ni=1∑hk=1ckIk(xi) 4.3.2*大延迟问题1|B,dis_cpt|Lmax ∑ni=1∑hk=1ckIk(xi) 4.3.3*大完工时间问题1|B,dis_cpt|Cmax ∑ni=1∑hk=1ckIk(xi) 4.4工件可拒绝排序问题 4.4.1工件可拒绝的分批排序问题1rej,B∑j∈ej Cmax 4.4.2带权总完工时间排序问题1rej∑j∈ej ∑j∈SwjCj 第5章供应链排序问题 5.1供应链排序问题简介及数学模型 5.2树状供应链排序问题 5.2.1总流程问题1→G,Pm‖∑Fj ∑Dgyg 5.2.2辅助问题的构造及其求解 5.3网状供应链排序问题 5.3.1供应商问题 5.3.2制造商问题 第6章双代理排序问题 6.1单台机器的双代理问题1‖ε∑wjVAj(σ):∑CBj(σ) 6.1.1问题的复杂性 6.1.2问题的动态规划算法 6.2自由作业的递推刻画 6.2.1问题O2‖CAmax(σ):CBmax(σ) 6.2.2*小化*大完工时间加权和问题O2‖CAmax αCBmax 第7章动态规划刻画FPTAS 7.1序关系和问题描述 7.2ex-benevolent问题 7.2.1两台同型机下的时间表长问题P2‖Cmax 7.2.2两台同型机下的总权完工时间问题P2‖∑wjCj 7.2.3具有时间相关加工时间的两台同型机的总完工时间问题 P2time-dep|∑Cj 7.3cc-benevolent 问题 7.3.1单机下加权误工工件个数问题1|batch|∑wjUj 7.3.2单机下退化效应相关的时间表长问题1|Deteriorate|Cmax 7.3.3单机下误工损失问题1‖∑Vj 7.3.4单机下加权误工损失问题1‖∑wjVj 7.4本章小结 参考文献 附录英汉排序与调度词汇 索引