工件具有加工位置上限及完工截止期的单机排序问题研究

目录

声明

第一章 绪论

1.1 引言

1.2 记号和规则

1.3 计算复杂性

1.4 可行性检测

1.5 相关文献综述

1.5.1 工件具有加工位置上限的排序

1.5.2 工件可退化排序

1.5.3 多代理排序

1.5.4 多指标排序

1.6 本文结果

第二章 工件具有加工位置上限及完工截止期的单机排序问题

2.1 引言

2.2 最小化最大位置延迟和正则指标的 Pareto 排序问题

2.2.2 问题 1|-kj,-dj|#(L(V)max ,f)

2.3 问题1|-kj,pj(t)=αj(α+bt),-dj,prec|f

第三章 工件具有加工位置上限的单机排序问题

3.1 引言

3.2 问题 1|rj, -kj,pj(t)=αj(a+bt), prec|f

3.2.1 问题 1|rj, -kj,pj(t)=αj(a+bt), prec|f

3.2.2 问题 1|rj, -kj,pj(t)=αj(a+bt)|f

3.2.3 NP-困难性证明

3.3 问题 1|ND, -kj,pj(t)=αj(a+bt)|#(∑Cj(A),f(B)max)

3.3.1 Pareto 排序问题的若干规则

3.3.2 问题 1|ND,-kj,pj(t)=αj(a+bt)|∑Cj(A):f(B)max≤Q

3.3.3 问题 1|ND,-kj,pj(t)=αj(a+bt)|#(∑Cj(A):f(B)max)

3.4 最小化总完工时间和总加权违反预期位置上限工件数目

3.4.1 问题 1|-kj|∑wjVj

3.4.2 问题 1|-kj|λ1∑Cj+λ2∑wjVj

3.4.3 问题 1|-kj|Lex(∑Cj,∑wjVj)

3.4.4 问题 1||Lex(∑Cj,∑wjVj)

第四章 工件具有完工截止期的单机排序问题

4.1 引言

4.2 最小化总误工时间问题

4.3 最小化总误工量问题

4.4 工件具有相同工期最小化总加权误工量问题

4.4.1 NP-困难性证明

4.4.2 动态规划算法

4.4.3 全多项式时间近似方案

4.4.4 问题 1|dj =d, -dj|∑Yj

4.5 最小化违反预期位置上限工件数目问题

4.5.1 NP-困难性证明

4.5.2 情形 1

4.5.3 情形 2

4.6 工件具有到达时间且加工可中断最小化总完工时间问题

4.6.1 预备知识

4.6.2 NP-困难性证明

4.7 问题 1|CO|∑Cj(A)∶∑Uj(B)≤Q

4.7.1 文献中的逻辑错误及反例

4.7.2 NP-困难性证明

第五章 结论与展望

参考文献

在学期间论文发表情况

致谢