批处理机调度问题的模型与优化方法研究
发布时间：2020-07-28 13:15
【摘要】：批处理机调度是调度问题的一个重要分支。不同于经典调度问题,在批处理机调度问题中,一台机器可以同时加工多个工件。由于这类调度问题不仅需要将工件指派到机器上,还包含将工件分批的决策问题,因此比经典调度问题更为复杂,很多已知的批调度问题均是NP难解问题。 批处理机调度在现实生产环境中有着广泛的应用,包括半导体芯片生产,钢铁制造,货物运输等。合理的调度方案可以大幅提高生产效率,节省生产成本,因此对批处理机调度问题的研究有着重要的现实意义。 尽管当前已有不少文献对批处理机调度问题进行研究,但这些研究仍然有着不足之处。一是研究的问题主要侧重于工件具有相同尺寸的较简单情形,较少涉及不同尺寸工件情况。二是求解方法多是设计精确求解算法解决小规模问题或是用简单启发式算法获得近似解,对于复杂的构造式方法较少有人研究。三是研究的目标集中在以makespan为代表的生产效率型目标,而对于调度问题中的能源效率则鲜有关注。 针对当前研究中存在的问题,本研究主要做了以下工作: (1)从聚类视角下研究了不同尺寸工件批处理机调度问题。论证了差异工件单机环境下的批调度问题实质为一种广义聚类问题,为求解该问题提供了一个新的途径。提出了批的空间浪费比的概念,将最小化C max的目标函数变换为最小化批的加权空间浪费比,从而可以更容易地寻找启发式信息指导分批过程,两者的等价性也在文中给出了证明。此外,以批的空间浪费比为基础,进一步定义了批间的距离度量,提出了批的约束凝聚聚类算法CACB,并通过实验验证了算法的有效性。 (2)将不同尺寸工件的批处理机调度问题推广到工件动态到达的并行机环境,提出并证明了该问题的两个不同下界。在此基础上设计了两种智能优化算法。一是基于工件序列编码的遗传算法,通过工件序列和Best-Fit规则生成分批,并设计了一个ERT-LPT算法来安排批在机器上的加工。另外一种是基于构造式分批的蚁群算法,算法同时考虑工件在尺寸和加工维度的特点作为启发式信息,指导蚂蚁不断寻找适合的工件加入当前批,直到所有分批构造完毕。对两种算法的性能及偏好,通过大量仿真实验进行了比较。 (3)将能源效率问题融入调度领域的研究中。构建了在分时电价条件下,以最小化电力成本和makespan为目标的柔性流水车间批调度问题的模型。设计了三种不同的多目标优化算法来求解该问题:即偏好向量蚁群系统PVACS,基于NSGA-II和基于SPEA2的进化算法,并比较了三种算法在不同评价指标下的性能。
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2011
【分类号】：F273;F224
【图文】：
仿真实验进行了比较。（3）考虑电力成本的柔性流水车间批调度问题的建模与多目标优化研当前制造业的一个研究热点就是绿色制造问题。而在生产调度领域，电在总生产成本中占据较高比重。如何在及时完成生产任务的前提下进行度，降低制造企业的电力成本，是极具现实意义的问题。本文以铝片生产制造为背景，构造了在分时电价条件下，柔性流水车间的批调度问题模型。以最小化最大完工时间和电力成本为目标，设计了SGA-II（Non-dominated Sorting Genetic Algorithm - II），SPEA2（Strento Evolutionary Algorithm 2）的多目标优化算法。并将用户偏好融入到多群算法的搜索过程，提出了 PVACS（Preference VectorAnt Colony Syste，并比较了三种算法在不同指标下的性能。2 结构与内容安排本文的研究主要以算法为主线展开，论文的总体结构如图 1.2 所示。
图 2.1 聚类问题描述尽管如此，通常的聚类算法不能直接用于求解批调度问题，两者还有着明显的差别：（1）目标函数不同。传统聚类算法的目标一般是最小化簇内差异，而最大化簇间差异，因此，其目标函数一般为以下形式(Pinter and Pesti, 1991)：KpPDFDSDSKK()min||{(),,()}||1=…∈πX (2.11或abpPRFRSSabKKK( )=max||{(,),1≤≤≤}||∈πX (2.12其中aS 表示第 a 个簇， ()aD S是其直径， (,)abR SS是簇 a 和簇 b 间的距离或相异度。Kπ 表示将对象划分为 K 个子集的所有聚类方案的集合， {,,}K1 KP = SS是聚类的结果，符号p|| ||为pl 模。而分批问题的目标是最小化各批总加工时间。（2）距离或相异度度量不同。传统聚类问题多用欧氏距离或 Minkowski距离(Xu and Wunsch, 2005)：nndDistancexx1/|| = ∑ (2.13
图 2.2 具有不同利用率和负载均衡率的两个批a由 2 个工件组成，加工时间和尺寸均为 ( 6,8)和 (1 ,1)。假设机器容批 a 的利用率 =0.900aUR ，负载均衡率 =0.286aBR ；批 b 由 3 个工件 ( 6,2)， (3 ,2)和 (1 ,6)。则批b 的利用率 =1.0bUR ，负载均衡率 =0.bBR a。但显然，批a造成的浪费要明显小于批b 。因此，很可能会出均利用率和平均负载均衡率都好于方案乙，目标函数值却劣于方此外，因为批的利用率和负载均衡率分别从不同角度定义，两者的度量标准，也难以进行比较和统一。此，本文提出批的空间浪费比的概念，并以此为基础，给出聚类度量。义 2.1 批b 中由于工件加工时间差异使机器加工该批时造成的浪费空间，其量纲用工件的加工时间 p与工件尺寸s的乘积来度量下：∑= jjbIWS (b )(pp)s
本文编号：2772930
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2011
【分类号】：F273;F224
【图文】：
仿真实验进行了比较。（3）考虑电力成本的柔性流水车间批调度问题的建模与多目标优化研当前制造业的一个研究热点就是绿色制造问题。而在生产调度领域，电在总生产成本中占据较高比重。如何在及时完成生产任务的前提下进行度，降低制造企业的电力成本，是极具现实意义的问题。本文以铝片生产制造为背景，构造了在分时电价条件下，柔性流水车间的批调度问题模型。以最小化最大完工时间和电力成本为目标，设计了SGA-II（Non-dominated Sorting Genetic Algorithm - II），SPEA2（Strento Evolutionary Algorithm 2）的多目标优化算法。并将用户偏好融入到多群算法的搜索过程，提出了 PVACS（Preference VectorAnt Colony Syste，并比较了三种算法在不同指标下的性能。2 结构与内容安排本文的研究主要以算法为主线展开，论文的总体结构如图 1.2 所示。
图 2.1 聚类问题描述尽管如此，通常的聚类算法不能直接用于求解批调度问题，两者还有着明显的差别：（1）目标函数不同。传统聚类算法的目标一般是最小化簇内差异，而最大化簇间差异，因此，其目标函数一般为以下形式(Pinter and Pesti, 1991)：KpPDFDSDSKK()min||{(),,()}||1=…∈πX (2.11或abpPRFRSSabKKK( )=max||{(,),1≤≤≤}||∈πX (2.12其中aS 表示第 a 个簇， ()aD S是其直径， (,)abR SS是簇 a 和簇 b 间的距离或相异度。Kπ 表示将对象划分为 K 个子集的所有聚类方案的集合， {,,}K1 KP = SS是聚类的结果，符号p|| ||为pl 模。而分批问题的目标是最小化各批总加工时间。（2）距离或相异度度量不同。传统聚类问题多用欧氏距离或 Minkowski距离(Xu and Wunsch, 2005)：nndDistancexx1/|| = ∑ (2.13
图 2.2 具有不同利用率和负载均衡率的两个批a由 2 个工件组成，加工时间和尺寸均为 ( 6,8)和 (1 ,1)。假设机器容批 a 的利用率 =0.900aUR ，负载均衡率 =0.286aBR ；批 b 由 3 个工件 ( 6,2)， (3 ,2)和 (1 ,6)。则批b 的利用率 =1.0bUR ，负载均衡率 =0.bBR a。但显然，批a造成的浪费要明显小于批b 。因此，很可能会出均利用率和平均负载均衡率都好于方案乙，目标函数值却劣于方此外，因为批的利用率和负载均衡率分别从不同角度定义，两者的度量标准，也难以进行比较和统一。此，本文提出批的空间浪费比的概念，并以此为基础，给出聚类度量。义 2.1 批b 中由于工件加工时间差异使机器加工该批时造成的浪费空间，其量纲用工件的加工时间 p与工件尺寸s的乘积来度量下：∑= jjbIWS (b )(pp)s
【引证文献】
相关博士学位论文 前1条
1 胡常伟;不一致熔炼任务的平行机批调度问题研究[D];广东工业大学;2013年
相关硕士学位论文 前2条
1 宋浩;智能优化算法在考虑加工成本的多目标差异工件平行机批调度问题中的应用研究[D];安徽大学;2014年
2 朱鑫;平行多机模具热处理车间动态批调度方法研究[D];广东工业大学;2014年
本文编号：2772930
本文链接：https://www.wllwen.com/jingjilunwen/hongguanjingjilunwen/2772930.html
