摘 要

装配作业车间调度是生产中常见的生产组织形式，具有复杂的物料清单结构（BOM）包含多层装配节点，其生产调度更加有挑战性。与传统的作业车间调度相比，目前对其研究相对较少,有重要的研究意义。

论文针对装配作业车间调度问题提出了三种求解算法：粒子群算法（PSO），基于浓度抑制的免疫粒子群算法（IPSO）和采用“精英替代”策略的粒子群算法（EIPSO）。并通过大量计算验证三种算法的优劣性。

论文的主要内容包括三种算法的设计思路和具体程序实现，以及最后的算例分析。最后的程序在Visual Studio.Net 2012编程环境下用VB语言进行了实验和数据分析。在算例设计阶段，设计了有不同装配层次的装配产品结构，以验证三种算法在不同问题规模和问题复杂度情况下的表现。

通过大量的数据分析，发现在问题相对简单时，PSO和两种基于免疫的算法（IPSO、EIPSO）的差别比较小；但是当问题规模增大时，如果给定比较合理的搜索时间，IPSO和EIPSO基本上都能够找到比PSO更好的解。

另外，在论文研究之初，我们预计由于EIPSO采取了“精英替代”策略，其效率将会比IPSO好。然而计算结果表明，EIPSO并没有表现更好。这表明，“精英替代”策略由于减少了粒子的多样性，容易导致比IPSO更多地陷入局部最优解.但是IPSO相对于PSO，其特有的浓度抑制机制是有效的，IPSO在择优选择的前提下，避免了高浓度粒子的过度复制，以降低收敛速度为代价提高了全局搜索能力。

关键词：装配作业车间调度问题；免疫粒子群优化算法；粒子群算法；“精英替代”策略；

Abstract

Assembly job shop scheduling (AJSS) is a common form of production organization, characterized by complex bill of materials(BOM) and multi-level assembly structure. The scheduling of AJSSP is more challenging compared to traditional job shop scheduling (JSS). However, the research of AJSS is much less than JSS, making it a more deserving future research area.

This paper proposes three algorithms for AJSS: particle swarm optimization (PSO), immune particle swarm optimization (IPSO) based on concentration inhibition concept, and IPSO incorporating elite preserving technique (EIPSO).

This research mainly includes the design and implementation of the three above algorithms, together with the final numerical analysis. The programming is done in Visual Studio.Net 2012 environment using VB language. In designing the experiment, different forms of assembly jobs are tested to compare the performance of three algorithms under different problem sizes and complexities.

Through comprehensive data analysis, it is found that PSO performs comparably with IPSO and EIPSO. However, for larger problems and with reasonable time allowance, IPSO and EIPSO generally can find better results than PSO.

At the beginning of this research, we expect that EIPSO will perform better than IPSO because of the introduction of elite preservation. However, numerical results prove EIPSO does not perform better. The elite strategy causes the algorithm to be more easily trapped in local optimum because it reduces partial diversity. But compared to PSO, IPSO performs better because of it concentration inhibition mechanism. This mechanism prohibits over production of high density particles without violating the principle of selecting the best, thus increasing the ability of IPSO for global optimum searching than PSO.

Key Words：Assembly Job Shop Scheduling（AJSS）；Immune Particle Swarm Optimization (IPSO)；Particle Swarm Optimizer(PSO)；Elite preservation and substitution strategy

目 录

第1章 研究背景及意义 1

1.1 研究背景 1

1.2 研究意义 1

第2章 装配作业车间调度问题研究 4

2.1 装配作业车间调度问题概述 4

2.2 装配作业车间调度问题的研究方法及现状 4

2.2.1 派工法则的研究 4

2.2.2 启发式算法研究 6

第3章 传统粒子群算法与免疫算法 7

3.1 粒子群算法 7

3.1.1 粒子群优化算法的原理 7

3.1.2 粒子群优化算法的流程 8

3.1.3 粒子群优化算法的研究现状 10

3.2 免疫算法 11

第4章 装配作业车间调度问题的免疫粒子群算法实现 13

4.1 免疫粒子群算法 13

4.2 装配作业车间调度问题的具体应用 14

4.2.1 装配作业车间调度问题的免疫粒子群算法设计 14

4.2.2 重要研究指数及公式 16

4.2.3 基于装配作业车间的免疫粒子群的编程设计及算法步骤 17

4.2.4 调试过程及结论 17

第五章 结论 24

参考文献 26

致 谢 30

第1章 研究背景及意义

1.1 研究背景

随着现代社会的日益发展，稻盛和夫提出了“现代企业的竞争已不再是单个企业的竞争，而是供应链之间的竞争”，而这一观点也被越来越多的人所认同。生产制造部分作为供应链中至关重要的部分，是现代企业提高资源利用率，提高企业运行效益的关键环节之一。企业能否在按时完成所有任务的情况下，合理分配好生产制造系中的所有资源，从而缩短生产制造过程中所花费的时间、降低生产成本是决定企业是否具备核心竞争力的重要问题。

在现代制造业迅速发展的大背景下，多品种、小批量、有不同完工时间要求的产品生产逐渐取代大批量、单类型的产品制造计划。企业为了满足市场需求变幻莫测这一趋势，把目标设定为缩短产品周期时间、降低生产成本、提高产品质量和提高机器设备的利用率等。在激烈的竞争中，企业想要占有一席之地，优化资源配置是至关重要的。因此企业必须着眼于提高生产效率，将有效的生产调度方式应用于实际的生产作业调度中去。也正是如此，作业车间调度问题（Job Shop Scheduling Problem, JSP）的研究具有更加重要的现实意义。

作业车间调度是组合优化及生产等领域的研究热点，其复杂性和挑战性在过去几十年吸引了无数研究者对该问题进行广泛而持久的研究。随着各种交叉学科的发展和对车间调度问题研究的深入，越来越多新的车间调度理论和方法被提出^[1]。然而，传统的作业车间调度问题研究忽略了装配关系，其产品只包含顺序加工工序，一个产品以一定的顺序经过不同的机器加工即可完成。但是在实际生产中，还存在着装配产品。一个装配产品包含很多装配工序，装配工序只有在所有前序工序完成之后才能进行，这就需要协调不同前序工序的进度，导致生产管理更加复杂。本文研究的调度问题既包括加工工序又包括装配工序，我们称其为装配作业车间调度问题(Assembly Job Shop Scheduling Problem, AJSSP)。