USST_Arts_112480754基于学习效应的置换流水车间调度问题研究

VIP免费

3.0 赵德峰 2024-11-11 6 4 2.14MB 66 页 15积分

侵权投诉

摘要

调度是一个短期的决策过程，它将有限的生产资源合理分配给不同的任务，

在生产制造系统以及信息处理系统中占有重要地位。一个好的调度方案可以使企

业获得更高的生产效率及经济效益，能够提高企业的市场竞争力。目前，对于生

产调度的研究主要有两个方面：一是对调度问题进行建模；二是对求解调度问题

的算法进行设计。流水车间调度问题是研究最广泛的调度问题之一，有很强的工

程应用背景。而置换流水车间调度问题是比较典型的一类流水车间调度问题，它

主要在以单件大批量形式加工的制造型企业中存在。在生产调度问题的理论研究

中，置换流水车间调度问题因形式简洁，关联性广泛以及计算复杂度高成而成为

研究的热点。

学习效应是一个获得经验的过程，它发生在重复性的做一件相同或者相似的

工作时。在经典的排序理论中，人们将工件的加工时间看做一个常数。然而，在

实际生产过程中，工人和机器在连续加工同种或者同类工件时，由于学习效应的

存在，导致越往后加工，加工工件所用的时间越短，使得工件的累积平均完成时

间比理论值短。本文将学习效应模型加入到置换流水车间调度问题中，研究分析

学习效果对加工指标的影响程度，具有重要的理论价值和应用价值。

本文首先对国内外相关研究现状做了详细概述，然后分别建立基于学习效应

的单目标和多目标置换流水车间调度问题的模型，接着探索设计了萤火虫膜算法

对建立的模型进行测试求解：通过与萤火虫算法和粒子群算法的对比，验证了萤

火虫膜算法求解置换流水车间调度问题具有可行性和有效性，然后用 Car 类测试

问题测试得到不同学习率下置换流水车间调度问题的最大完工时间及总流经时间，

并分析得出学习效应对单目标和多目标置换流水车间调度问题的影响程度。

关键词：置换流水车间调度学习效应学习率萤火虫膜算法单

目标多目标

ABSTRACT

Scheduling is a short-term process of making decision. Limited resources

are allocated to different tasks rationally by scheduling. It plays an important role in

the manufacturing system and information processing system. A good scheduling

scheme can make the enterprise get higher production efficiency and economic benefit

and improve the market competitiveness of enterprises. At present, the production

scheduling research mainly has two areas: The first one is modeling the scheduling

problem; the second one is designing algorithm to solve the scheduling problem. Flow

shop scheduling problem is one of the most extensive research in scheduling problems,

and it has a strong engineering application background. And permutation flow shop

scheduling problem is a typical kind of flow shop scheduling problem, it is especially

suitable for manufacturing enterprises which have single mass production background.

In the theoretical study of the scheduling problem, permutation flow shop scheduling

problem with simple form, extensive relevance and high level of computation

complexity has became the hot research area.

The learning effect is a process of gaining experience. It happens when doing the

same or similar work repeatedly. In the classical theory of sorting, the processing time

of a workpiece is a constant. However as the existence of learning effect when we

make the same or similar workpiece in the processing workshop, the

following workpiece will be finished in a shorter time. This paper adds the learning

effect model to the permutation flow shop scheduling problem, studies and analysis the

influence of learning effect on the manufacturing. The research has important

theoretical value and application value.

At first, this paper made a detailed overview about the present situation of

domestic and foreign related research, and then model single objective and

multi-objective permutation flow shop scheduling problem based on the learning effect,

and then explore and design the fireflies membrane algorithm to test our model: by

contrast with the firefly algorithm and particle swarm optimization algorithm, verified

the feasibility and effectiveness of firefly membrane algorithm to solve the permutation

flow shop scheduling problem, and then use ‘Car’ test problems to get the makespan

and total flow time of permutation flow shop scheduling problem under different

learning rate, and get the effect degree of the influence in single objective and

multi-objective permutation flow shop scheduling problem.

Key Words: Permutation flow shop scheduling problem, Learning

effects, Learning rate, Firefly membrane algorithm, Single objective,

Multi-objective

中文摘要

ABSTRACT

第一章绪论„„„„„„„„„„„„„„„„„„„„„„„„„„„„„1

1.1 课题的来源、研究目的及意义„„„„„„„„„„„„„„„„„„1

1.1.1 课题的来源„„„„„„„„„„„„„„„„„„„„„„„1

1.1.2 课题的研究目的„„„„„„„„„„„„„„„„„„„„„1

1.1.3 课题研究的意义„„„„„„„„„„„„„„„„„„„„„1

1.2 国内外研究现状 „„„„„„„„„„„„„„„„„„„„„„„ 2

1.2.1 PFSP 的研究现状„„„„„„„„„„„„„„„„„„„„„2

1.2.2 多目标优化问题的研究现状„„„„„„„„„„„„„„„„3

1.2.3 学习效应的研究现状„„„„„„„„„„„„„„„„„„„4

1.2.4 膜算法的研究现状„„„„„„„„„„„„„„„„„„„„5

1.3 论文主要研究内容与框架 „„„„„„„„„„„„„„„„„„„6

第二章调度及算法研究综述„„„„„„„„„„„„„„„„„„„„„„8

2.1 PFSP 的问题描述 „„„„„„„„„„„„„„„„„„„„„„„8

2.2 求解 PFSP 的算法概述 „„„„„„„„„„„„„„„„„„„„„9

2.3 膜计算优化算法„„„„„„„„„„„„„„„„„„„„„„„ 13

2.3.1 生物细胞膜的基本结构和功能 „„„„„„„„„„„„„„13

2.3.2 膜计算基本理论 „„„„„„„„„„„„„„„„„„„„14

2.3.3 膜计算的基本描述 „„„„„„„„„„„„„„„„„„„15

2.3.4 膜计算的规则 „„„„„„„„„„„„„„„„„„„„„17

2.4 萤火虫算法„„„„„„„„„„„„„„„„„„„„„„„„„ 18

2.4.1 萤火虫算法的研究现状 „„„„„„„„„„„„„„„„„18

2.4.2 萤火虫算法的原理 „„„„„„„„„„„„„„„„„„„18

2.4.3 萤火虫算法的数学描述 „„„„„„„„„„„„„„„„„19

2.4.4 算法设计 „„„„„„„„„„„„„„„„„„„„„„„19

2.4.5 算法流程 „„„„„„„„„„„„„„„„„„„„„„„21

2.4.6 仿真测试 „„„„„„„„„„„„„„„„„„„„„„„ 22

2.5 本章小结„„„„„„„„„„„„„„„„„„„„„„„„„„ 23

第三章基于学习效应的单目标置换流水车间调度问题研究 „„„„„„„„24

3.1 学习曲线模型„„„„„„„„„„„„„„„„„„„„„„„„ 24

3.2 基于学习效应的 PFSP 模型的构建„„„„„„„„„„„„„„„„27

3.3 单目标萤火虫膜算法„„„„„„„„„„„„„„„„„„„„„ 27

3.3.1 算法设计 „„„„„„„„„„„„„„„„„„„„„„„27

3.3.2 算法参数讨论 „„„„„„„„„„„„„„„„„„„„„29

3.3.3 仿真测试 „„„„„„„„„„„„„„„„„„„„„„„30

3.4 模型的求解与分析 „„„„„„„„„„„„„„„„„„„„„„33

3.5 本章小结„„„„„„„„„„„„„„„„„„„„„„„„„„ 36

第四章基于学习效应的多目标置换流水车间调度问题研究 „„„„„„„„37

4.1 多目标优化问题的描述 „„„„„„„„„„„„„„„„„„„„37

4.2 基于学习效应的 MPFSP 模型的构建 „„„„„„„„„„„„„„„39

4.3 多目标萤火虫膜算法 „„„„„„„„„„„„„„„„„„„„„40

4.3.1 多目标 Pareto 最优解集的构建„„„„„„„„„„„„„„40

4.3.2 聚集距离 „„„„„„„„„„„„„„„„„„„„„„„41

4.3.3 局部搜索算法的设计 „„„„„„„„„„„„„„„„„„42

4.3.4 膜内多目标萤火虫算法的设计 „„„„„„„„„„„„„„43

4.3.5 多目标萤火虫膜算法的总流程 „„„„„„„„„„„„„„44

4.4 模型的求解与分析 „„„„„„„„„„„„„„„„„„„„„„46

4.5 本章小结 „„„„„„„„„„„„„„„„„„„„„„„„„„54

第五章总结与展望 „„„„„„„„„„„„„„„„„„„„„„„„„55

参考文献„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„57

在读期间公开发表的论文和承担科研项目及取得成果„„„„„„„„„„„62

致谢 „„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„ 63

第一章绪论

1.1 课题的来源、研究目的及意义

1.1.1 课题的来源

本课题来源于国家自然科学基金资助项目：“行为驱动、学习效应嵌入的

TFT-LCD 调度建模及智能优化研究-基于有限理性及中国情景的视角”，(项目编

号：71271138)。

1.1.2 课题的研究目的

本文针对置换流水车间调度问题(Permutation Flow-shop Scheduling Problem,

PFSP)，考虑生产实际情况，将学习效应模型加入到 PFSP 中，建立基于学习效应

的PFSP 模型，并设计嵌套有萤火虫算法的膜算法来对含有学习效应的单目标

PFSP 和多目标 PFSP 进行求解，并与不含学习效应时两种情况下的问题结果进行

比较分析，找出差距，为制造企业提供理论依据。

1.1.3 课题研究的意义

近年来，生产调度问题作为当前研究的一个热点问题，被广泛地研究。生产

调度问题包括单机调度问题(Single Machine Scheduling，SMS)、流水车间调度问

题(Flow-shop Scheduling Problem, FSP) 、作业车间调度问题(Job-shop

Scheduling problem, JSP)以及开放车间调度问题(Open-shop Scheduling Problem，

OSP)等。据相关资料统计表明：大约有 25%的制造系统、信息服务系统可以用流

水车间调度模型来表示。

在实际生产车间中，PFSP 是流水车间调度问题中重要的一类调度问题，主要

存在于以单件大批量生产为主的制造类企业。PFSP 不仅有工程背景，还是一个经

典的理论问题，它形式简洁：所有工件按照同一种排序依次通过每一台机器；关

联性广泛：是很多生产调度问题的缩影；计算复杂度很高：当机器数大于 2时已

是NP 难题。因此，该问题一直是学术界和工程领域的研究热点，找到求解该问

题的有效方法，对于提高企业的生产效率和生产资源的利用率、提高企业竞争能

力具有非常重要的意义。

在经典的排序理论中，人们通常将工件的加工时间设置为常数，而不考虑与

工件的加工位置之间的关系。然而，在实际生产的过程中，工人和机器在加工同

上海理工大学硕士学位论文

种或者同类工件任务时，不断积累经验，导致加工的效率逐渐提高，被排在后面

加工的工件加工所用的时间变少，工件的平均加工时间变短，我们将这种带有学

习性质的现象称为学习效应(learning effect)。学习效应是一个获得经验的过程，它

发生在重复性的做一件相同或者相似的工作时。学习的效果是工人会用更少的时

间或者更低的成本来完成这项任务。

将学习效应模型加入到 PFSP中，研究分析学习效果对加工指标的影响程度，

具有重要的理论研究价值和应用价值。本文探索设计萤火虫膜算法来对单目标和

多目标 PFSP 问题进行求解，寻找能够更好的算法来解决生产调度问题。

1.2 国内外研究现状

1.2.1 PFSP 的研究现状

在对单目标 PFSP 的研究中，研究最多的优化指标是最小化最大完工时间

(makespan)。对最小化最大完工时间的优化能够缩短产品的生产周期，提高机器

利用率，有助于企业在现有资源有的条件下生产效率和经济效益的提高。目前对

单目标 PFSP 问题的研究主要集中在求解方法的研究上。经过几十年的发展，研

究方法从简单到复杂。通过文献分析，对单目标 PFSP 的求解方法，有以下三种

类型：精确方法、启发式算法以及智能优化算法。其中，精确方法主要有：多项

式方法(Polynomial Algorithm) 、数学规划法 (Mathematical Programming) 、分支

定界法(Branch and Bound)和拉式松弛算法(Lagrangian Relaxation)等；启发式方法

主要包括 Johnson 算法、Nawaz-Enscore-Han(NEH）算法、Palmer 算法、Gupata 算

法以及 Campbell-Dudek-Smith (CDS)算法[1]。研究表明，精确算法只适用于求解

小规模调度问题，启发式算法求解质量较差[2]，而当m>2 时，PFSP 问题已是 NP

难题[3]，因此随着问题规模的增加，调度问题的解空间容量巨大，其求解过程更

加复杂。由于精确方法和启发式算法的局限性，目前对该问题的求解方法趋向于

使用更高效的智能优化算法，包括遗传算法(Genetic Algorithm,GA)、禁忌搜索算

法(Taboo Search,TS)、模拟退火法(Simulated Annealing,HS)、蚁群优化算法(Ant

Colony Optimization,ACO)以及粒子群算法(Particle Swarm Optimization,PSO)等[4]。

近些年来大量学者对求解 PFSP 的智能算法进行了研究。何建佳等[5]将文化算

法融入到量子粒子群算法中，同时结合遗传算法的交叉及变异操作，提高了算法

的全局搜索能力，在 PFSP 问题上取得了不错的效果；刘延风、刘三阳[6]对微粒

群算法进行改进，采用贪婪随机自适应元启发式算法构造多个初始解，并对每次

迭代生成的最优解进行局部搜索，改进后的算法性能优良；唐海波等[7]提出了一

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要调度是一个短期的决策过程，它将有限的生产资源合理分配给不同的任务，在生产制造系统以及信息处理系统中占有重要地位。一个好的调度方案可以使企业获得更高的生产效率及经济效益，能够提高企业的市场竞争力。目前，对于生产调度的研究主要有两个方面：一是对调度问题进行建模；二是对求解调度问题的算法进行设计。流水车间调度问题是研究最广泛的调度问题之一，有很强的工程应用背景。而置换流水车间调度问题是比较典型的一类流水车间调度问题，它主要在以单件大批量形式加工的制造型企业中存在。在生产调度问题的理论研究中，置换流水车间调度问题因形式简洁，关联性广泛以及计算复杂度高成而成为研究的热点。学习效应是一个获得经验的过程...

展开>> 收起<<

USST_Arts_112480754基于学习效应的置换流水车间调度问题研究.pdf

共66页,预览7页

还剩页未读，继续阅读

USST_Arts_112480754基于学习效应的置换流水车间调度问题研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: