考虑缓冲和运输能力限制的作业车间和跨单元生产调度方法

摘要

随着生产水平的提高，以及需求的多元化，生产模式由大批量集中生产逐渐转为多品种，变批量生产。近年来市场的竞争越来越激烈，企业不得不从多方面考虑节约生产成本，如设备的使用率，占地空间以及产品库存的大小等因素，而产品工艺路线复杂程度的增加导致产品在不同设备之间的转移逐渐成为不可忽视的因素，将直接影响到生产效率的高低。由于单个车间的设备局限性，企业内部不同车间的生产协作现象出现次数越来越频繁，针对不同车间（单元）之间的协作行为很难迅速做出高质量的调度方案。车间（单元）之间的协作生产效率高低与复杂程度将直接影响到企业生产的质量，各单元在空间位置上的不同分布使得单元之间的运输成为单元协作生产中一个不可避免的重要环节。 本文在对车间调度和单元调度的现状进行分析与综述的基础上，针对影响调度的因素以及现存的生产问题提炼出科学问题进行研究，为企业的实际生产调度提供理论依据。本文作为国家创新研究群体科学基金(No.71021061)、国家自然科学基金(No.71420107028)的重要组成部分，主要研究工作包括以下几个方面: (1)针对面向设备缓冲空间有限情况下的Job Shop调度问题进行了研究，对于企业来说，减少设备占地空间是节约成本的有效方法之一。以最小化make-span为目标，建立非线性整数规划模型，提出基于非连通图的两阶段邻域搜索算法进行求解，通过测试40组benchmark算例，验证了算法的有效性，通过比较不同设备缓冲空间下的同一算例得到的结果，讨论了缓冲空间的变化对最终调度造成的不同影响; (2)针对面向运输能力有限下的Blocking Job Shop调度问题进行了研究，既是对上面问题的深入研究，同时减少使用不同设备之间运输资源也能很大程度上节约生产成本。以最小化make-span为目标，基于是否考虑起始运输点两种情况，分别建立了非线性整数规划模型。在前人的成果基础上，从加工设备的视角提出了新式非连通图，完善并提出新的相关性质;基于此提出联合improved timetabling的两阶段邻域搜索算法进行求解，通过测试96组benchmark算例并与Lingo计算得到的结果进行比较，验证了算法的有效性; (3)在现实生产中，运输资源往往是有限的，不同单元之间运输是跨单元中不可避免的重要环节。针对面向运输能力有限下跨单元生产的零部件调度问题，以最小化make-span为目标，建立非线性混合整数规划模型，将问题分解为两个子问题:即Intra-CPS和Inter-CPS问题;针对两个子问题，分别提出了基于邻域搜索的遗传算法和基于轮盘赌的启发式算法求解。通过测试随机算例并与CPLEX和其他算法进行比较，验证了算法的有效性; (4)针对运输能力充足下跨单元生产不同单元之间的合作问题进行了研究，通过引入成熟的机制，使得单元之间具有更高的合作效率，从而提高调度方案的质量。以最小化make-span为目标，建立非线性整数规划数学模型，围绕不同单元之间如何进行合作，提出了基于拍卖的跨单元生产的零部件调度方法，通过测试算例证明了算法的有效性，稳定性，并通过灵敏的分析讨论了参数对算法的影响。

目录

声明

摘要

第一章绪论

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

1．2研究目标与研究内容

1．2．1研究目标

1．2．2研究内容

1．3研究的技术路线与方法

1．4主要研究成果

第二章车间调度和单元调度及算法的研究综述

2．1车间调度问题概述

2．1．1车间调度的分类

2．1．2车间调度的规则与性能指标以及考虑因素

2．1．3车间调度问题的研究现状与求解方法

2．2单元生产问题概述

2．2．1单元生产的基本概念与产生背景

2．2．2单元生产的特征与优势

2．2．3单元生产的发展阶段

2．3单元调度问题及算法综述

2．3．1单元调度的基本概念与问题描述

2．3．2单元调度问题的研究现状

2．4本章小结

第三章面向设备缓冲空间有限情况下的Job Shop调度问题

3．1问题的提出

3．2设备缓冲空间有限下Job Shop问题的研究现状

3．3设备缓冲空间有限下Job Shop问题的描述与模型

3．3．1设备缓冲空间有限下Job Shop问题的描述

3．3．2设备缓冲空间有限下Job Shop问题的模型

3．4基于邻域搜索求解JS-LOB问题的两阶段算法

3．4．1基于NEH和缓冲空间调度机制的启发式算法

3．4．2基于非连通图的邻域搜索算法

3．5实验结果与分析

3．5．1实验设计与参数设置

3．5．2结果与分析

3．6本章小结

第四章面向运输能力有限下的Blocking Job Shop调度问题

4．1问题的提出

4．2 Blocking相关调度问题研究现状

4．3运输能力有限下的Blocking Job Shop调度问题(BJS-AGV)

4．3．1运输能力有限下的Blocking Job Shop调度问题

4．3．2运输能力有限下的Blocking Job Shop调度问题的数学模型

4．4基于邻域搜索求解BJS-AGV问题的两阶段算法

4．4．1基于timetabling和AGV调度机制的启发式算法

4．4．2基于新式非连通图的邻域搜索算法

4．5实验与结果分析

4．5．1实验设计与参数设置

4．5．2结果与分析

4．6本章小结

第五章运输能力有限下的跨单元生产调度问题

5．1问题的提出

5．2跨单元生产的零部件调度问题研究现状

5．3运输能力有限下跨单元生产的零部件调度问题与模型

5．3．1运输能力有限下跨单元生产的零部件调度问题的描述

5．3．2运输能力有限下跨单元生产的零部件调度问题的模型

5．4基于邻域搜索求解单元内Intra-CPS调度的遗传算法

5．4．1初始化编码与解码

5．4．2适值计算

5．4．3交叉操作

5．4．4变异操作

5．4．5邻域搜索

5．5基于轮盘赌求解单元间Inter-CPS调度的启发式算法

5．6实验与结果分析

5．6．1实验设计与参数设置

5．6．2结果与分析

5．7本章小结

第六章基于拍卖的跨单元生产调度方法

6．1问题提出

6．2拍卖理论在生产调度领域的研究现状

6．3跨单元生产的零部件调度问题描述与模型

6．3．1跨单元生产的零部件调度问题描述

6．3．2跨单元生产的零部件调度问题数学模型建立

6．4求解M-CPS问题的拍卖算法

6．4．1准备拍卖

6．4．2竞标书收集

6．4．3时间点估价

6．4．4二次竞标

6．4．5决定赢家

6．4．6参考矩阵

6．5关于拍卖过程的算例说明

6．6实验与结果分析

6．6．1实验设计和参数设置

6．6．2结果与分析

6．7本章小结

第七章结束语

参考文献

致谢

攻读博士期间发表的论文