多代理生产调度问题的理论研究

摘要

生产调度是指对给定的一组工件和多台机器，在满足生产工艺的约束下，确定每台机器上工件的顺序与时间，以使得能源、资源或效率等指标达到最优。以往的调度研究主要集中在所有工件作为一个整体考虑一致的性能指标作为目标。但是随着经济的发展和人们消费水平的提高，顾客对商品的个性化和多样化的需求越来越高，传统的调度理论已不再适合这种新的需求情况下的调度问题。所以迫切需要研究考虑顾客多样性需求的多代理生产调度问题。 多代理生产调度是指每个顾客的需求对应一个代理，所有代理竞争在共同的机器上同时加工各自的工件，使得每个代理的目标达到最优。本文以钢铁生产中不同生产阶段的工艺过程为背景，提炼出多代理生产调度中一系列问题。针对带有依赖于时间恶化工件的双代理单机调度问题、带有线性恶化工件的双代理单机批处理机调度问题、单机批处理机上多代理合作博弈问题、以及带有线性恶化工件的双代理两台机器车间调度问题进行了理论研究。对于上述问题，分别进行了复杂性分析;对于可解问题，给出了最优算法或分配机制;对于难解问题，给出了NP-难证明，对难解问题的特殊情况，分析了最优解的结构特征和性质，构造了多项式或伪多项式时间的求解方法。具体内容概括如下: 1)针对带有线性恶化工件和释放时间的双代理单机调度问题，考虑了工件释放时间相同与不同两种情况如下:(1)当工件释放时间相同时，针对最小化代理A的总加权拖期工件个数使得代理B工件完工时间的最大费用不超过一个给定上界的问题，证明了问题的NP-难性。对于代理B工件完工时间的最大费用为最大完工时间的特殊情况，分析了最优解性质，给出了伪多项式时间动态规划算法进行求解;对于代理A的所有工件具有相等权值特殊情况，通过分析可中断问题的最优解结构与性质，给出了求解问题的多项式时间最优算法。(2)当工件释放时间不同时，针对最小化代理A的总拖期工件个数使得代理B的总拖期工件个数不超过一个给定上界的问题，证明了问题在不同数量释放时间与工期情况下的NP-难性。对于所有工件具有一致的释放时间与工期，或同一代理的工件具有相同恶化率和一致的释放时间与工期两种特殊情况，分析了最优解性质，分别给出了多项式时间动态规划算法进行求解。 2)针对带有依赖于时间恶化的工件及机器维护的单机双代理调度问题，考虑了依赖于工件的学习效应与不依赖于工件的学习效应两种情况，其中工件的学习效应是指工件的加工时间随着加工位置的延后而减小，如下:(1)当依赖于工件的学习效应时，针对最小化工件提前惩罚、拖期惩罚、共同工期窗开始时间费用、以及工期窗大小费用之和问题，分析了最优解性质，将问题转换为指派问题，进而在多项式时间求得最优解。对于问题的三个特殊情况，分析了最优解的结构，分别给出了更为有效的求解方法。(2)当不依赖于工件的学习效应时，针对最小化总加权完工时间与最大延迟两个问题，分别证明了在满足一定条件下WSPT与EDD规则仍可求得问题的最优解。 3)针对带有线性恶化工件的双代理单机有界批处理机调度问题，基于工件的释放时间相同与不同，以及工件组批时两个代理的工件可以在同一批的兼容性与不可在同一批的不可兼容性，考虑了不同情况下目标函数为最小化代理A工件的最大完工时间（或总拖期工件个数）使得代理B工件的最大完工时间（或总拖期工件个数）不超过一个给定上界的八个不同问题的时间复杂性。对于可解问题，给出了多项式时间最优算法;对于难解问题，给出了NP-难证明，对难解问题的一般情况或特殊情况，分析了最优解性质，给出了伪多项式或多项式时间的求解方法。 4)针对带有线性恶化工件的双代理单机无界批处理机调度问题，基于工件组批时两个代理的工件可以在同一批的兼容性与不可在同一批的不可兼容性，考虑了工件释放时间相同与不同两种情况如下:(1)当工件释放时间相同时，针对最小化代理A工件完工时间的总费用使得代理B工件完工时间的最大费用（或总费用）不超过一个给定上界的问题，分析了问题的最优解性质，分别给出了动态规划算法求得最优解;(2)当工件释放时间不同时，针对最小化代理A工件的最大完工时间使得代理B工件的最大完工时间不超过一个给定上界的问题，分析了最优解的结构与性质，给出了最优解的求解方法。 5)针对单机批处理机上多代理生产调度的合作博弈问题，研究了多代理生产调度的最优解，设计了多代理合作节省费用的合理分配机制，证明了多代理合作博弈与工件合作博弈核的存在性。对于多代理生产调度的特殊情况，证明了对应的多代理合作博弈与工件合作博弈均为凸博弈。 6)针对带有线性恶化工件的双代理两台机器车间调度问题，分别考虑了流水车间、开放车间、以及异序作业车间环境下，目标函数为最小化代理A工件的最大完工时间使得代理B工件的最大完工时间不超过一个给定上界的问题时间复杂性。对于流水车间，证明了问题的NP-难性，对具有优势机器关系的两个特殊情况，分别给出了最优算法。对于开放车间与异序作业车间，分别证明了问题的NP-难性。

目录

声明

摘要

第1章绪论

1．1问题的研究背景及意义

1．2多代理生产调度问题的研究现状

1．3本文的研究路线及主要工作

1．3．1本文的研究路线

1．3．2本文的主要工作

第2章带有线性恶化工件和释放时间的双代理单机调度问题

2．1引言

2．2问题描述

2．3工件释放时间相同的情况

2．3．1最小化代理A总加权完工时间，代理B最大费用为约束的情况

2．3．2最小化代理A总加权拖期工件数，代理B最大费用为约束的情况

2．3．3最小化代理A总加权拖期工件数，代理B总加权拖期工件数为约束的情况

2．3．4最小化代理A总加权提前惩罚，代理B最大提前惩罚为约束的情况

2．4工件释放时间不同的情况

2．4．1最小化代理A最大完工时间，代理B最大完工时间为约束的情况

2．4．2最小化代理A总完工时间，代理B最大完工时间为约束的情况

2．4．3最小化代理A总拖期工件数，代理B总拖期工件数为约束的情况

2．5小结

第3章带有依赖于时间恶化的工件及机器维护的单机双代理调度问题

3．1引言

3．2问题描述

3．3依赖于工件的学习效应情况

3．3．1最小化工件最大完工时间的情况

3．3．2最小化工件总完工时间的情况

3．3．3最小化工件总完工时间绝对差值的情况

3．3．4最小化工件总提前、拖期、工期窗开始时间、工期窗大小费用的情况

3．4不依赖于工件的学习效应情况

3．4．1最小化工件总加权完工时间的情况

3．4．2最小化工件最大延迟的情况

3．5小结

第4章带有线性恶化工件的双代理单机有界批处理机调度问题

4．1引言

4．2问题描述

4．3工件释放时间相同的情况

4．3．1最小化代理A最大完工时间，代理B最大完工时间为约束的情况

4．3．2最小化代理A总拖期工件数，代理B总拖期工件数为约束的情况

4．4工件释放时间不同的情况

4．4．1最小化代理A最大完工时间，代理B最大完工时间为约束的情况

4．4．2最小化代理A总拖期工件数，代理B总拖期工件数为约束的情况

4．5小结

第5章带有线性恶化工件的双代理单机无界批处理机调度问题

5．1引言

5．2问题描述

5．3工件释放时间相同的情况

5．3．1最小化代理A最大费用，代理B最大费用为约束的情况

5．3．2最小化代理A总费用，代理B最大费用为约束的情况

5．3．3最小化代理A总费用，代理B总费用为约束的情况

5．3．4最小化代理A总拖期工件数，代理B总拖期工件数为约束的情况

5．3．5最小化代理A总拖期工件数，代理B最大费用为约束的情况

5．4工件释放时间不同的情况

5．4．1最小化代理A最大完工时间，代理B最大完工时间为约束的情况

5．4．2最小化代理A总拖期工件数，代理B总拖期工件数为约束的情况

5．5小结

第6章单机批处理机上多代理生产调度的合作博弈问题

6．1引言

6．2多代理批生产调度问题描述

6．3多代理批生产调度合作博弈

6．4特殊情况

6．5小结

第7章带有线性恶化工件的双代理两台机器车间调度问题

7．1引言

7．2问题描述

7．3流水车间的情况

7．3．1 NP-难的证明

7．3．2两个可解的特殊情况

7．4开放车间的情况

7．5异序作业车间的情况

7．6小结

第8章结论

参考文献

致谢

作者博士期间发表和录用的论文

作者博士期间参与的科研项目