考虑机器使用成本的同类机调度问题

摘要

本文基于云制造的背景，研究了考虑机器使用成本的同类机调度问题。制造业作为我国的支柱产业，自从改革开放以来，持续快速发展，与制造强国的差距很大。云制造是新兴信息技术与制造业相结合所产生的一种新型制造模式。实体制造资源通过云制造平台线上使用权交易，线下生产制造，能够实现分散异址制造资源的有效整合，从而实现制造资源与服务的开放协作、高度共享，以降低制造资源的浪费，对我国制造业具有至关重要的意义。云制造的实质是通过互联网实现制造资源的共享，因此在云制造环境下，生产调度必须考虑到机器使用成本。
　　本文假定生产周期内机器的使用成本是固定的，研究了一类考虑机器使用成本的同类机调度问题，调度目标是在总成本预算范围内，最小化最大完工时间，以期达到生产成本与生产效率的平衡。首先我们假定了所有作业都是标准作业，即作业的加工时间相同，同时考虑了不可中断和可中断两种情形，我们通过对问题进行分析可知该问题是NP-hard的，针对不可中断情形，我们在ECT规则基础上提出了启发式算法H1算法，并证明了其最大误差界为2[1+1/(h-1)];针对可中断情形，我们提出了启发式算法H2算法，并证明了其最大误差界为1+1/(h-1)，其中，h是在选机器中第一次跳过的机器。最后通过大量的编程数据实验表明了这两个算法的有效性。
　　接着，本文研究了作业为普通作业（即作业的加工时间不同）时的考虑机器使用成本的同类机调度问题。我们的目标函数同样是在总成本预算范围内，最小化makespan。通过对问题进行分析可知该问题是NP-hard的。我们同时考虑了不可中断情形和可中断情形，针对不可中断情形，基于对经典的LPT算法的改进，提出了一个MLPT算法。理论证明了该算法的最大误差界是2[1+1/（h-1）]，其中，h是在选机器中第一次跳过的机器。最后也通过大量的编程数据实验表明了该算法的有效性。针对可中断情形，我们在Level算法的基础上提出了启发式算法H3算法来解决它。

目录

声明

致谢

摘要

第一章 绪论

1．1 研究背景

1．2 研究意义

1．3 论文的研究思路及内容

1．4 章节安排

第二章 相关概念及理论基础研究

2．1 相关概念研究

2．2 相关理论基础研究

第三章 面向标准作业的考虑机器使用成本的同类机调度问题

3．1 问题描述

3．2 不可中断问题

3．2．1 算法设计

3．2．2 算法分析

3．2．3 算例

3．3 可中断问题

3．3．1 算法设计

3．3．2 算法分析

3．3．3 算例

3．4 实验数据及分析

第四章 面向普通作业的考虑机器使用成本的同类机调度问题

4．1 问题描述

4．2 不可中断问题

4．2．1 算法设计

4．2．2 算法分析

4．2．3 算例

4．3 可中断问题

4．3．1 算法设计

4．3．2 算例

4．4 实验数据及分析

5．1 论文工作总结

5．2 展望

参考文献

攻读硕士学位期间的学术活动及成果情况