客户订单总完成时间最小化调度问题研究

摘要

随着面向订单生产或装配以及大规模定制生产方式的推广,客户订单调度问题成为了调度研究的新领域,该类问题考虑了多个客户订单,而每个订单可以包含一个或多个产品,订单的完成时间由最后完成产品所决定,这些特征使得订单调度问题不再是单独产品的排序过程,而是多个关联任务资源配置的决策过程。订单调度问题的思考来源于现实的生产问题,具有广泛的应用背景和研究意义。
　　客户订单调度问题包括了简单的单机和复杂的多机环境问题,而多机环境又进一步分为专用机和柔性机两种情况。在单机订单调度问题中,与总完成时间相关的客户订单的调度问题类似于多阶段生产调度问题,考虑到同一台机器处理不同产品需要额外的调整时间,本文在此基础上增加了换产时间约束,使得该问题更具有现实意义。在多机环境中,绝大部分的订单调度问题被证明了是NP-难的,本文着力于设计启发式算法来提升计算效率,同时也会对算法的最坏情况作出相应的证明和分析。在实际生产应用中,与总完成时间相关的目标函数是具有普遍性的优化标准,这也是本论文研究的重点。
　　本论文研究了特殊条件下订单调度问题的复杂度,挖掘了其结构特征,针对单机问题开发多项式时间可解算法,对多台专用机问题设计了用于求得上界的启发式启发算法,在此基础上使用禁忌搜索算法寻找更优解;对多台柔性机问题设计了先订单后产品的两阶段调度算法。实例验证说明,这些算法具有较高的求解效率并且其中部分算法能实现较优的优化目标。

目录

封面

声明

中文摘要

英文摘要

目录

第1章绪论

1.1研究背景

1.2应用意义

1.3框架与符号

1.4研究方法

第2章文献综述

2.1客户订单调度的单机情况

2.2订单调度的多机问题

第3章带换产时间的单机订单调度问题

3.1问题介绍

3.2基本引理

3.3算法设计

3.4算法步骤

3.5算例分析

3.6本章小结

第4章多台专用机订单调度问题

4.1问题介绍

4.2基本引理

4.3算法规则说明与分析

4.4算法优化设计

4.5结果分析

4.6本章小结

第5章多台完全柔性机订单调度问题

5.1问题介绍

5.2算法设计

5.3复杂度分析

5.4算法最差情况分析

5.5算法运行与对比

5.6本章小结

第6章总结与展望

参考文献

致谢