作业车间调度模型
基于WSA算法的作业车间低碳调度方法研究
1.1 引言
本章主要研究了以最大化完工时间和能耗指标为目标的作业车间低碳调度模型的求解方法。首先，建立了多目标作业车间低碳调度模型；然后基于Pareto 支配理论，设计了一种高效的MODWSA算法获得满意的Pareto非支配解；最后，设计了一套测试算例，将MODWSA算法与其它经典多目标算法进行比较分析，验证了MODWSA算法的优越性。在本研究中，作者完成了两项工作：首先，构建了一个新的多目标作业车间低碳数学模型；其次，设计了一种高效的MODWSA算法获得满意的Pareto非支配解。
1.2 作业车间低碳调度模型
本章研究的作业车间低碳调度问题可描述如下：对给定的n个工件及k台机器，一个工件的加工需要经过m道工序，每道工序允许在特定的机器上加工，任意一台机器在任意一个时刻仅能加工某一工件的某一道工序，并且一个工件只能在其上道工序完成后下一道工序才能开始加工[插入文献]。
考虑机器的准备时间，准备时间与同一机器上相邻两工件的加工顺序相关，并且机器的启动和工件的加工是相连的。对应于不同工序，机器具有不同的速率档位进行加工，并且可以进行调节。从能耗的角度来看，机器有四种不同的状态：加工状态(机器在加工工件)，启动状态（机器在准备加工一个新的工件），待机状态（机器处于空转中），以及关机状态（机器被关机）。通常情况下，当机器在较高速率运作时，工件的加工时间会被缩短，但是相应的能耗会增加。因此本问题以最大化完工时间和能耗指标为目标，由于本章所研究问题的特点，该问题要比传统的作业车间调度问题要复杂的多。在该问题中，其它设定如下：
●工件在车间里被连续加工。也就是说，加工过程不能被中断。
●机器允许有空闲时间，并且各阶段间具有容量无限的缓冲区。
●当有第一个工件在机器上加工时，机器开机；当在该机器上加工的所有工件
加工完毕后，机器关机。
●机器速度在工件加工过程中不能进行调整。
1.2.1 混合整数规划模型
为了提出问题的数学模型，根据上面对问题的描述，我们首先定义了下面的相关数学符号。
符号定义:
I ：工件集合，{1,,,}I i n =??。
J ：工序集合，{1,,,,}J j m =??。
M ：机器集合，{1,,,,}M k l =??。
ij M ：工件i 的第j 道工序所在的加工机器。
k
Ω：机器k 上所有工件及其对应工序的集合，即{(,)|}k ij i j M k Ω==。
,,k i j v p ：工件i 的第j 道工序在机器k 上以速度v 加工所需的时间。
'k i i s ：在机器k 上，工件i’加工完成后紧接着工件i 加工所需准备时间。当'0,i =0=0
k
i s 表明了当工件i 是分配到相关机器的第一个工件，且准备时间为0。
,k v pp ：机器k 在速度v 下运行所消耗的功率。
'i i sp ：机器k 由工件i’转到工件i 所消耗的启动功率。 k ip ：机器k 保持空转所消耗的功率。
决策变量:
,i j b ：工件i 的第j 道工序的开始加工时间。 ,i j e ：工件i 的第j 道工序的结束加工时间。
,,k i j v x ：二维决策变量，当工件i 的第j 道工序在机器k 上以速率v 加工时，值为1；
否则值为0。
'k i i y ：二维决策变量，当工件i 紧接在工件i’后在机器k 上加工时，值为1；否则
值为0。
on k T ：辅助决策变量，表明了机器k 的开机时间。 off k T ：辅助决策变量，表明了机器
k 的关机时间。
基于这些定义的数学符号，下面给出了流水车间低碳调度问题的混合整数规划模型。 目标函数:
Min max ,max i m i I
C e ∈=
(1) Min 123TEC E E E =++
(2) 1,,,,,k
k k i j v k v i j v i I j J v V E x pp p ∈∈∈=??∑∑∑
(3) 2''''k k k i i i i i i i I i I
E y sp s ∈∈=??∑∑
(4)
3'',,,,'k off on k k k k
k k i i i i i j v i j v k k M i I i I i I j J v V E T T y s x p ip ∈∈∈∈∈∈??=
--?-?? ? ???
∑∑∑∑∑∑ (5)
目标（1）表明了最大完工时间最小。目标（2）表明了总能耗最小，其中1E 表
示机器处于加工状态时的总能耗，2E 表示机器处于启动状态时的总能耗，3E 表示了机器处于待机状态时的总能耗。他们分别对应了公式（3）-（5）. 约束：
,,1,,,k
k i j v ij v V x
i I j J k M ∈=?∈∈=∑
(6) ,,,,,,,,,k
k k i j i j i j v i j v ij v V e b p x i I j J k M ∈=+??∈∈=∑
(7)
{},,10,,2,,i j i j b e i I j m --≥?∈∈?
(8) ''y y 1,
,',k k
i i ii i i I k M +≤?∈∈
(9)
',',',,',',(',')'0,,,=i i i i i i k
k k k i j i j i j i j i I
b e y s y i I j J k M ∈Ω∈-
?-?≥?∈∈∑∑
(10)
,(,)min k
on k i j i j T b ∈Ω=
(11)
,(,)max k
off k i j i j T e ∈Ω=
(12)
,,{0,1};,,k i j v k x i I j J v V ∈?∈∈∈
(13)
',{0,1};i i y ∈
,'i i I ?∈
(14)
,,0,0,,i j i j e b i I j J >≥?∈∈
(15)
其中，约束（6）保证每个工件遍历所有工序，并且对应于特定工序，每个工件被分配到一台机器上，并以一种速度级别进行加工。约束（7）表示在加工过程中不允许中断，工件必须在一台机器上以一种速度级别加工完毕。约束（8）确保只有在工件的前一道工序完成之后下一道工序才能开始。约束（9）和（10）保证机器容量限制，即只有在完成了前一个工件的加工之后，才能开始下一个工件的加工。约束（11）表示辅助变量的计算，它等于分配给相应机器的工件的起始时间的最小值。约束（12）表示辅助变量的计算，它等于分配给相应机器的工件的结束时间的最大值。约束（13）—（15）分别定义了决策变量的可行范围。 1.2.2 举例说明
举例进行说明问题（带甘特图的那种）
1.3 MODWSA 算法求解作业车间低碳调度问题
从上一章WSA 算法的简述中可以看出，作为一个求解连续性问题的算法，WSA 算法同样不能直接用于求解离散的作业车间调度问题，因此需要设定合理的编码和解码方式、距离计算公式和移动策略。在这一节中，提出了一种多目标离散鲸鱼群算法（MODWSA ），以解决作业车间低碳调度问题，算法框架流程如图1所示：
参数设置和父代
种群PG 初始化
评价每个个体
G =G +1, 满足终止条件？
对PG 中每个个体i ：寻找其 较优且最近 个体是否存在？
对个体速度向量进行邻域搜索
速度向量移向个体i 的 较优且最近 个体
生产子代种群OG ，合并PG 和OG 生成种群RG
对RG 采用非支配排序和拥挤距离排序更新父代种群PG
输出Pareto 解
对个体i 的工序向量采用交叉算子
对个体i 的工序向量采用变异算子
图1 MODWSA 求解作业车间低碳调度流程图
MODWSA 算法包含了模拟鲸鱼群觅食的行为，MODWSA 主要包含了以下四个步骤：初始化、工序向量更新操作，速度选择寻找“较优且最近”的鲸鱼Y 、应用速度更新操作算子对速度向量进行更新操作，具体步骤如下所示：
Step 1：初始化。首先给出参数设置，如种群大小等，然后随机初始化鲸鱼群，对鲸鱼群中的每个个体进行适应度评价。
Step 2：工序更新操作。采用二元锦标赛方法选择父代个体，随机选择母代
个体，对父代与母代的工件序列执行交叉变异等基本操作，得到子代的工件序列。
Step 3：寻找离父代个体“较优且最近”的鲸鱼。针对速度向量部分，计算与父代个体最近的较优个体，设定为鲸鱼Y。
Step 4：速度更新操作。父代个体的速度向量向鲸鱼Y的速度向量进行迁移操作生成子代个体的速度向量，使子代个体的速度向量向鲸鱼Y的速度向量方向移动。
Step 5：精英保留策略[插入文献]。合并种群大小为N的副本种群和相同大小的子代种群，这样得到一个大小为2N的混合种群，评价改混合种群根据非支配排序和拥挤距离技术选择出前N个较好的个体作为下一次迭代更新的父本，并淘汰余下的N个个体。具体操作过程如下图2所示。
P G+1
P G
O G
图2基于非支配排序和拥挤策略的更新操作
1.3.1 编码与解码策略
编码方式是MODWSA算法求解调度问题的首要和关键任务。传统的JSP问题中应用较多的是基于工序的编码，它具有任意置换染色体后总能得到可行调度、避免死锁、对解空间表征的完全性能和解码成主动调度等优点[插入文献]。对于传统调度问题，加工时间是固定不变的，但本章所研究的低碳作业车间调度问题的加工时间是可以根据加工机器的速度改变进行选择的，所以需要处理工件排序和每个工件对应的速度选择两个子任务。因此，本章提出了双层编码机制以适应问题的特征，该编码机制包含了两层信息。第一层基于工序编码，表示工件的加工顺序，记作π，其中每个工件的工序都用相应的工件序号表示，从左到右扫描序列，工件序号第k次出现，表示加工该工件的第k道工序；第二层表示每个工件每道工序的加工速度，记作N。为了说明这个编码机制，本章给出一个规模为2工件3工序的实例，如下所示：
[]
π=
1,2,1,1,2,2
[]
1,3,2,3,2,2
N=
在这个编码中，π表示工件每道工序的加工顺序，其中3π表示工件1的第2道工序在
工件1的第1道工序和工件2的第1道工序之后加工。N表示工件每道工序的加工速度，
其中3N 表示工件2的第1道工序在对应机器21M 上以速度3进行加工。举例进行说明，
列出加工时间以及功率消耗。
解码是将编码转化为调度解的过程。为了将一个解决方案解码成一个可行的时间表，需要解决2个问题。一个问题是安排工件的加工顺序，另一个问题是确定每道工序对应机器的加工速度。设u 为编码任意一个工件i 的第j 道工序,i j O ，加工时间为u P ，且工序u 的开始加工时间为u BT ，则完工时间为u u BT P +；设工序的工件紧前工序和机器紧前工序分别为
u JP 和u MP （如果存在）
，那么工序u 的开始加工时间由它的工件紧前工序和机器紧前工序中完工时间的最大值决定。所有工件从0时刻开始加工，在解码过程中工序u 开始加工时间的计算公式为：
max(,)u u u u u JP JP MP MP BT BT P ST P =++
如果是工件i 的第一道工序，则没有紧前工序，则工件i 的第一道工序的开始时间u BT 计算公式为：
u u u MP MP BT ST P =+
可以看出转化编码为工序及其速度选择向量后，可依据上面2公式进行解码，得到该编码的半主动调度解。此外，本章将一种插入式贪婪解码算法引入到低碳作业车间调度问题，使编码解码后产生主动调度。该插入式贪婪解码算法解码方法如下：
首先将编码看作工序的有序序列，根据工序在该序列上的顺序进行解码，将每道工序按选择的加工速度插入到该工序加工机器上的最佳可行加工时刻进行加工，按此方式知道序列上所有工序都安排在其最佳可行的地方。（可以举图例进行说明）
1.3.2 种群初始化
基于以上的双层编码机制，对种群进行初始化。基于本章的描述，种群的每一个个体由一个工序向量和一个速度向量构成。其中工序向量由工件和其对应工序决定，随机生成；速度向量则根据对应工序的加工机器可选速度，随机生成。
1.3.3 工序向量更新操作
对应于编码的2个不同部分——工序向量和机器加工速度向量，本文采用不同的进化策略来更新编码的2个不同部分。
对应于工序向量部分，采用传统的交叉和变异算子进行操作。交叉算子可以探索解空间的未知区域。对于解的第一层（即π），采用优先操作交叉算子（Precedence Operation Crossover ，POX ）[插入文献]来更新工序向量部分，具体的交叉步骤如下：
Step 1：把所有工件随机分成2个集合1J 和2J ，
Step 2：复制父代1P 包含在1J 中的工件到子代C （保留顺序）
， Step 3：复制父代2P 包含在2J 中的工件到子代C （保留顺序）
，得到子代C 。
交叉操作示意图如下所示：
1
2
1
2
3
3
121323
112323
父代P1
父代P2
子代C
J 1={1}；J 2={2,3}
3 工
序交叉操作
在变异阶段，从工序向量中选择两个不同工件的任意一道工序，交换其在序列中的位置。给出变异操作的具体过程实例：初始的工序向量为π = (1, 2, 1, 3, 2, 3)，选择工件1的第1道工序和工件2的第2道工序（即第1和第5位置点）位置互换，交换后的工序向量变为π = (2, 2, 1, 3, 1, 3)。具体的图例如图4所示：
121323
221313
变异前
变异后
图4 工序变异操作
1.3.4 速度向量更新操作
针对速度向量，本研究选择使用WSA 算法中的移动算子来更新速度向量，使种群中每条鲸鱼的速度向量向离自己“较优且最近”的个体移动。其中选择离的最近的个体需要运用汉明距离进行计算。汉明距离最早在1950年由Richard W. Hamming [插入论文]提出来，目的是为了在以定长二进制数进行通信的过程中，统计数据位发生翻转的错误位数，因此，其也被叫作信号距离。汉明距离的主要思想是计算两条信息中不同位的个数。在编码部分采用离散个体编码方案中，个体之间的距离通过计算速度向量之间的汉明距离来表示，具体计算方法如下图所示：
112223
122124
V 1
V 2
图5 汉明距离计算图例
图中的例子显示，有3个对应位置速度不同，故此部分的汉明距离V d 是3。
选择“较优且最近”的个体，即是寻找适应度值较好，且离该鲸鱼汉明距离值最小的个体Y ，原鲸鱼的速度向量向鲸鱼Y 的速度向量方向移动。当不存在“较优且最近”的个体时候，则通过速度向量自我变异的方式进行移动。2种移动方式如下所示：
● 当较优且最近的存在：原鲸鱼的速度向量与鲸鱼Y 的速度向量进行交叉操作。随机选
择2个交叉点，将鲸鱼Y 的速度向量中2个交叉点之间的部分复制到原鲸鱼的速度向量中，具体交叉操作如图6所示：
223123
113234
父代鲸鱼
鲸鱼Y
213223
子代鲸鱼
图6 速度向量交叉操作
● 当种群中不存在较优且最近的个体时，按照变异的方式移动。首先从速度向量中随机选
择一道工序改变其速度值为另一可行的速度值（对应于加工该工序的机器）；然后选择使用相同加工机器的2道工序互换它们的加工速度。具体变异操作如图7所示：
223123
243321
变异前
变异后
图7 速度向量变异操作
1.4 实验仿真与分析
数学建模--车间作业调度问题
一、二维背包问题 一维背包问题讨论的背包问题只有一种限制，即旅行者所能承受的背包的重量（亦即重量不能超过a （kg ）.但是实际上背包除受重量的限制外，还有体积的限制，这就是不但要求旅行者的背包的重量M 不能超过a （kg ），还要求旅行者背包的体积V 不能超过b （m3）,我们把这样的问题称为“二维背包问题”。 它的状态变量有两个因素:一个是重量，一个是体积。 二维背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i 件物品所需的两种代价分别为i a 和i b 。两种代价可付出的最大值（两种背包容量）分别为a 和b 。物品的价值为i c 。 模型： 11 1 max . ,1,2,3...n i i i n i i i n i i i i c x st a x a b x b x z i n ===≤≤∈=∑∑∑
例题 码头有一艘载重量为30t ，最大容为12×10m 3的船，由于运输需要,这艘船可用于装载四种货物到珠江口，它们的单位体积,重量及价值量见下表: 现求如何装载这四种货物使价值量最大。 1 1 1 max .,1,2,3...n i i i n i i i n i i i i c x st a x a b x b x z i n ===≤≤∈=∑∑∑ 可用动态规划来解决 1.设x i （i=1,2,3,4）分别表示装载这四种货物的重量， 2.阶段k ：将可装入的货物按1,2,3,…n 排序，每个阶段装一种货物，（共可分为四个阶段） 3.状态变量： 1k S +和1k R +，表示在第k 阶段开始时，允许装入的前k 种货物的重量与体积。 状态转移方程： 11k k k k k k k k S S a x R R b x ++=-=- ()(){}111,max ,j k k j k k j j f S R f S R c x -++=+，表示在不超过重量和体积的前提下，装 入前j 中货品的价值。（j=1,2,3,4）
一种环境感知的仿真服务调度模型
———————————— 基金项目基金项目：：国家自然科学基金资助项目(61163009, 61163010)。 作者简介作者简介：：张学军(1977－)，男，讲师、博士研究生，主研方向：服务计算，服务仿真；闫光辉、胡晓辉，教授。 收稿日期收稿日期：：2013-05-29 修回日期修回日期：：2013-07-21 E-mail ：zxjly1_new@https://www.sodocs.net/doc/12531336.html, 一种环境感知的一种环境感知的仿真服务调度模型仿真服务调度模型 张学军张学军，，闫光辉闫光辉，，胡晓辉 (兰州交通大学电子与信息工程学院，兰州 730070) 摘 要：针对传统分布式仿真框架HLA/RTI 中动态调度负载平衡较差、执行可靠性较低的问题，提出一种基于环境感知的仿真服务调度模型C3SM 。C3SM 模型包含总体结构、调度策略和服务部署。总体结构规定各个模块的功能与交互接口，调度策略采用改进的蚁群算法进行仿真服务的动态调度，服务部署采用重叠覆盖部署策略以保证较好的服务可用性和较低的资源消耗。仿真实验结果表明，与传统分布式仿真框架HLA/RTI 相比，C3SM 模型通过实时获取执行环境的上下文信息，能够获得较优的负载平衡度，且重叠覆盖的仿真服务部署策略使得仿真运行系统的可靠性明显提高。 关键词关键词：：环境感知；高层体系结构；分布式仿真；Web 服务；蚁群算法；仿真服务调度 A Context-aware Simulation Service Scheduling Model ZHANG Xue-jun, YAN Guang-hui, HU Xiao-hui (School of Electronics and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China) 【Abstract 】In order to address the problem of traditional distribution simulation framework HLA/RTI with respect to poor load balancing performance in service dynamic scheduling and low reliability of service execution, this paper proposes a Context-aware Simulation Service Scheduling Model(C3SM), which includes general framework, scheduling strategy and service deployment. The framework provides the functions and interaction interfaces of each module. For the scheduling scheme, a modified ant colony algorithm is used to achieve optimum load balancing and system reliability. Moreover, the overlapped coverage deployment strategy is adopted to obtain the high service availability and low resource consumption in the service deployment. Experiments are carried out on performance comparisons between the traditional HLA/RTI and C3SM in the scheduling strategy and the reliability of service performing, the results show that C3SM can obtain good load balance with the real-time context information of the execution environment, and the overlapped coverage simulation service deployment scheme greatly improves the reliability of the simulation execution system. 【Key words 】context-aware; High Level Architecture(HLA); distributed simulation; Web service; ant colony algorithm; simulation service scheduling DOI: 10.3969/j.issn.1000-3428.2014.03.019 计 算 机 工 程 Computer Engineering 第40卷 第3期 V ol.40 No.3 2014年3月 March 2014 ·体系结构与软件技术体系结构与软件技术·· 文章编号文章编号：：1000-3428(2014)03-0093-06 文献标识码文献标识码：：A 中图分类号中图分类号：：TP391.9 1 概述 随着计算机与信息技术的飞速发展，计算机仿真技术在智能交通、航空航天、生物、通信等领域得到了广泛的应用和研究。由于计算机仿真所涉及的问题越来越复杂，仅靠单个仿真系统已无法满足实际仿真需求。目前多种智能手持设备快速发展，具备了较强的计算能和通信能力，可以将多种手持设备与传统的服务器或PC 一起构成一个分布式、异构的智能仿真建模和运行环境。 高层体系结构(High Level Architecture, HLA)是分布式仿真领域的一个软件架构标准，它解决了仿真应用之间可交互性和模型在不同领域重用性的关键问题[1] 。但是，HLA 在应用中存在许多不足：(1)由于存在多个运行时基础设施(Runtime Infrastructure, RTI)厂商，不同厂商的RTI 基于特定的计算机平台与编程语言，互操作性和跨平台能力有限；(2)RTI 在运行时会受到防火墙的限制，使仿真任务无法正常运行；(3)RTI 对系统的容错性支持不足，单一联邦的失效会导致整个仿真任务的失败。 Web 服务(Web service)是一种面向服务的分布式计算模式，具有良好的平台异构性和语言独立性特点，可以与其他分布式计算技术相结合，且其请求和响应不受防火墙限制。因此，可以考虑将Web 服务和HLA 进行结合，克服HLA 的不足，进而构建一个具备一定冗余度的可靠分布式仿真系统。
作业车间调度模型
基于WSA算法的作业车间低碳调度方法研究 1.1 引言 本章主要研究了以最大化完工时间和能耗指标为目标的作业车间低碳调度模型的求解方法。首先，建立了多目标作业车间低碳调度模型；然后基于Pareto 支配理论，设计了一种高效的MODWSA算法获得满意的Pareto非支配解；最后，设计了一套测试算例，将MODWSA算法与其它经典多目标算法进行比较分析，验证了MODWSA算法的优越性。在本研究中，作者完成了两项工作：首先，构建了一个新的多目标作业车间低碳数学模型；其次，设计了一种高效的MODWSA算法获得满意的Pareto非支配解。 1.2 作业车间低碳调度模型 本章研究的作业车间低碳调度问题可描述如下：对给定的n个工件及k台机器，一个工件的加工需要经过m道工序，每道工序允许在特定的机器上加工，任意一台机器在任意一个时刻仅能加工某一工件的某一道工序，并且一个工件只能在其上道工序完成后下一道工序才能开始加工[插入文献]。 考虑机器的准备时间，准备时间与同一机器上相邻两工件的加工顺序相关，并且机器的启动和工件的加工是相连的。对应于不同工序，机器具有不同的速率档位进行加工，并且可以进行调节。从能耗的角度来看，机器有四种不同的状态：加工状态(机器在加工工件)，启动状态（机器在准备加工一个新的工件），待机状态（机器处于空转中），以及关机状态（机器被关机）。通常情况下，当机器在较高速率运作时，工件的加工时间会被缩短，但是相应的能耗会增加。因此本问题以最大化完工时间和能耗指标为目标，由于本章所研究问题的特点，该问题要比传统的作业车间调度问题要复杂的多。在该问题中，其它设定如下： ●工件在车间里被连续加工。也就是说，加工过程不能被中断。 ●机器允许有空闲时间，并且各阶段间具有容量无限的缓冲区。 ●当有第一个工件在机器上加工时，机器开机；当在该机器上加工的所有工件 加工完毕后，机器关机。 ●机器速度在工件加工过程中不能进行调整。 1.2.1 混合整数规划模型 为了提出问题的数学模型，根据上面对问题的描述，我们首先定义了下面的相关数学符号。
多台电梯调度算法设计及仿真
多台电梯调度算法设计及仿真 （安庆师范学院物理与电气工程学院安徽安庆 246011） 摘要：根据电梯群控系统的非线性，随机性，不确定性和离散动态性特点，采用面向对象的分析与设计方法和基于事件扫描的数字仿真方法，设计一个多台电梯调度算法，采用 Visual C++技术编程和OpenGL 可视化技术，并通过对电梯群的运行状态进行实时监测与分析，实现高层建筑电梯群调度和载客的活动仿真情况，评价电梯群的服务质量和运行效能。 关键词：电梯群控制系统，多台电梯调度算法，面向对象，数字仿真 1. 引言 电梯是现代立体交通的重要组成部分，随着高层建筑在世界范围内得以迅猛发展，极大地促使了电梯技术的改良和革新。近半个世纪以来，电梯技术已经从原始模型升降机发展到高级智能化电梯。而智能化要求电梯系统服务质量和服务效率能尽量提高建筑的有效利用率和性能。在建筑设计中，同常将多台电梯配置在一起，构成电梯群，集中为大楼提供服务，这就是电梯群控系统（EGCS, Elevator Group Controlystem）【1】。电梯群控系统是一个实时性非常强的系统，需要不断收集梯群的状态信息和厅外的召唤信号，采取一定的派梯策略，选择最合适的电梯去应答厅外召唤。为了节约开发成本，一个成功的电梯群控系统在应用到实际控制系统之前，往往都在计算机系统上进行仿真研究，调试参数，在仿真研究完成以后，在应用到电梯试验塔做实验，检验控制策略的有效性和有关的性能指标。电梯群控系统是通过对电梯群运行状态进行实时监测与分析，再根据不同的实际情况对电梯进行优化调度和合理分配，进而改善和提高电梯系统服务质量和服务效率【2】。 随着智能控制技术在电梯群控系统(EGCS)中的广泛应用,电梯交通系统设计的关键是满足乘客生理上和心理上的承受力,有效地解决高层建筑复杂的楼内垂直交通。一个设计良好的电梯群控系统必须具备在客流高峰时确保乘客在较短的侯梯时间和乘梯时间内到达目的地，在空闲时使电梯群运行消耗能量最低。我国电梯配置和电梯系统特征的研究与国外相比还处于落后的状态，虽然国内与1990年对电梯系统的动态特性进行了研究，但在电梯群控方面，仍有许多理论及技术问题亟待解决，因此开展电梯群控算法研究具有重要的理论和实际意义，这对电梯群控系统性能（安全性，舒适性等）是十分必要的，同时也可以改变我国目前电梯技术主要依赖于进口的不利局面【3】。 用计算机仿真研究电梯群的服务质量和运行效能，大楼的层高不要超过25层，电梯的总台数不要超过八台。设某办公大楼楼层为20层，有载客电梯5部（用电梯1—电梯5标识）。利用Visual C++技术编程和OpenGL可视化技术实现高层建筑电梯群调度和载客的活动仿真情况。 2.设计方案 2.1 设计规则： 为了实现电梯群调度和载客的活动仿真情况，采用两种方式对其仿真：（1）人工控制方式；（2）自动控制方式。 2.1.1人工控制方式： 这种方式是完全仿真真实电梯群情况，乘客自己决定到达电梯时候和选择需要到达的楼层以及电梯的开关门。这种方式通过可视化技术可以直观的观察乘客发送电梯请求后，电梯群的调度情况和各电梯的当前状态，包括电梯内人数，电梯运行趋势，电梯开关门状态和电梯所在楼层。这种方式下电梯群调度遵循的规则为：
制造业车间作业计划与调度研究
制造业车间作业计划与调度研究 车间作业计划（Production Activity Control，PAC）是依据主生产计划（MPS）而编制的具体执行工作方案，它把车间的生产任务落实到每个人、每台设备上，是车间组织生产的依据，也是企业管理中最重要的部分。PAC的实施贯穿于生产系统的各道工序，受很多因素的制约。随着生产规模的扩大和复杂程度的提高，PAC的实施与调度也出现了一些问题。本文应用车间作业调度方法，针对当前PAC与调度中存在的问题进行研究，为企业提供优化的生产作业排序和车间作业调度策略，从实践与理论方面提升PAC及其调度水平，以提高制造系统的运行效率，增强企业的市场竞争力。 PAC与车间调度的内涵与特点 PAC系统是一个高度复杂的系统，它有效地综合了机械、信息、网络等资源。制定PAC是为了使生产设备、物料、人员和信息四者匹配，实现车间均衡、协调、持续生产。在PAC生产执行过程中，决策部门需要根据车间的生产能力及其它资源的使用等反馈情况不断地调整PAC，而调整计划贯穿于企业生产活动的全过程。因此，要最大限度地发挥生产系统的柔性潜力，满足市场需求。 1.1 PAC与车间调度的界定与内涵 PAC的编制包括确定操作顺序、分配资源和制定期量标准等。PAC与车间调度问题是一个典型的任务集，包括资源集、约束条件集、性能指标集。其中，资源集包括人员、设备、工具和材料等，而每台设备可以完成一种或多种作业，不同设备能完成的作业集可能相同也可能不同；约束条件集用以规定生产过程中需要的条件，如任务的优先级、每个作业要求完成的时间、资源的能力、生产工艺、质量标准等；性能指标集用以规定生产过程中需要优化的目标，如生产周期、在制品量、订单交货期、资源利用率和生产成本等。每一个任务都包含一组需要执行的作业序列（工序），而这些作业序列需要占用系统的机器、工具等资源，并且必须按照一定的工艺顺序执行。 调度的目标是为作业合理分配资源，为每一个加工对象合理安排具体的加工顺序、路径、时间、制造设备资源和操作等，使内部和外部约束条件被满足，其中内部约束主要为企业的资源约束、能力约束和生产过程中的技术约束等；外部约束主要为订单规定的时间要求和品质要求等，同时使大部分生产性能指标得到优化。在有限产能、库存容量及资源的约束下，通过优化配置生产资源来提高PAC的可实施性以及生产过程的可计划性、可控性。而车间作业调度与控制则是实现生产高效率、高柔性和高可靠性的关键环节。 1.2 编制PAC的特点 在编制PAC过程中应考虑其如下特点： （1）实用性。以在制品加工进度为基础编制工序能力计划，使PAC紧跟生产现场，达到计划编制与生产节拍的和谐统一。PAC计划期短、计划内容具体、计划单位小等，具有可操作性强。 （2）合理性。综合上级计划、在制品进展情况、工序周期、工序时差和剩余工作量等因素，通过合理地排程方法，达到满足交付和有效利用资源的目的。
数学建模车间任务调度问题
数学建模车间任务调度问题 2008-08-11 15:10:53| 分类：|字号 数学建模培训讲座 数学建模历年赛题的分析与思考 主要内容： 1、CUMCM的历年赛题分析； 2、数学建模竞赛的发展趋势； 3、对数学建模的几点想法和思考； 4、参加数学建模竞赛的技巧; 5、近年竞赛题的简要分析与评述。 一、CUMCM历年赛题的分析 数学建模竞赛的规模越来越大, 水平越来越高；竞赛的水平主要体现在赛题水平的提高； 赛题的水平主要体现： （１）综合性、实用性、创新性、即时性等；
（２）多种解题方法的创造性、灵活性、开放性等； （３）给参赛者留有很大的发挥创造的想象空间。 纵览15年的本科组30个题目(专科组还有11个题目)，可以从问题的实际意义、解决问题的方法和题型三个方面作一些简单的分析。 一、CUMCM历年赛题的分析 1. CUMCM 的历年赛题浏览： 1992年:(Ａ)作物生长的施肥效果问题(北理工：叶其孝） (B)化学试验室的实验数据分解问题（复旦：谭永基） 1993年:(Ａ)通讯中非线性交调的频率设计问题（北大:谢衷洁） (Ｂ)足球甲级联赛排名问题（清华：蔡大用） 1994年:(Ａ)山区修建公路的设计造价问题（西电大：何大可） (Ｂ)锁具的制造、销售和装箱问题（复旦:谭永基等） 1995年:(Ａ)飞机的安全飞行管理调度问题（复旦:谭永基等） (Ｂ)天车与冶炼炉的作业调度问题（浙大:刘祥官等） 1996年:(A)最优捕鱼策略问题（北师大：刘来福）
(B)节水洗衣机的程序设计问题（重大：付鹂）1997年:(A)零件参数优化设计问题（清华：姜启源） (B)金刚石截断切割问题（复旦：谭永基等） 1998年:(A)投资的收益和风险问题（浙大：陈淑平） (B)灾情的巡视路线问题（上海海运学院:丁颂康）1999年:(A)自动化机床控制管理问题（北大：孙山泽） (B)地质堪探钻井布局问题（郑州大学：林诒勋） (C)煤矸石堆积问题（太原理工大学：贾晓峰） 2000年:(A)DNA序列的分类问题（北工大：孟大志） (B)钢管的订购和运输问题（武大：费甫生） (C)飞越北极问题（复旦：谭永基） (D)空洞探测问题（东北电力学院：关信） 2001年:(A)三维血管的重建问题（浙大：汪国昭） (B)公交车的优化调度问题（清华：谭泽光）
调度模型
基于LTE的系统级仿真平台设计 许猛 北京邮电大学信息与通信工程学院WCSN实验室，北京（100876） Email: xumengbupt@https://www.sodocs.net/doc/12531336.html, 摘要：在无线通信系统实际部署之前，要对它进行充分的研究与评估，系统级仿真是全面考察系统整体性能的最常用手段。本文主要讨论了系统级仿真的基本方法，介绍了系统级仿真的分类：静态仿真和动态仿真，并对系统级仿真的原理进行了详尽的阐述，给出了系统级仿真与链路级仿真的接口的设计。以LTE系统为例，介绍了系统级仿真的基本流程，给出了系统级仿真的各个模块的基本模型，如小区模型、天线模型、路径损耗模型、调度模型、链路自适应模型等，详细阐述了系统级仿真的整个过程。 关键词：LTE；系统级仿真；调度 中图分类号：TN92 1．引言 近年来，移动通信的发展十分迅速，人们的需求从以简单的语音通话，慢慢向着多媒体方向转变，如数据、图像、传真等。随着用户需求的转变，新的通信系统层出不穷。从第一代的模拟通信系统，发展到第二代的窄带数字移动通信系统，如GSM，CDMA等，再到第三代的宽带移动通信系统（3G），如TD-SCDMA、WCDMA及CDMA2000，以及下一代移动通信系统LTE，每一阶段都极大改善了用户的服务质量，提供了更加丰富的业务。[1] 通信系统部署之前，需要对其进行充分的评估，掌握系统的整体性能，才能更好的部署，提供更好的通信服务。系统级仿真提供了评估系统性能的一个很好的平台。利用系统级仿真平台模拟系统的工作过程，可以得到系统的网络容量、覆盖分析等指标，从而合理的估计网络的规模及投资的规模，控制建设成本。[2] LTE(Long Term Evolution,长期演进)项目是3G的演进，始于2004年3GPP的多伦多会议。LTE并非人们普遍误解的4G技术，而是3G与4G技术之间的一个过渡，是3.9G的全球标准,它改进并增强了3G的空中接入技术，采用OFDM和MIMO作为其无线网络演进的唯一标准。在20MHz频谱带宽下能够提供下行326Mbit/s与上行86Mbit/s的峰值速率。改善了小区边缘用户的性能，提高小区容量和降低系统延迟。本文主要以LTE系统为背景，介绍了系统级仿真的原理与方法。[5] 2 .系统级仿真原理及仿真框架 系统级仿真是对用户和系统行为的拟合，是从整个系统（包含多个小区和用户）的角度分析系统的覆盖、容量和系统的性能，对于系统的参数设置给予定量的分析，为无线网络的规划优化提供依据。[2] 系统级仿真方法有两种，分别为静态仿真（Static Simulations）和动态仿真（Dynamic Simulations）。静态仿真通过需要对快照（Snapshot）的分析来了解网络性能，他需要一定数量的网络快照。动态仿真就是让真实环境中用户和系统采取的主要行为方式在系统级仿真中都得到具体的模仿性体现。比如用户的起呼，掉话，行进，转弯，切换等，在这些动态行为的基础上，用统计的方法计算所要求的参数和结果。[2] 系统级仿真结果要依赖与链路级仿真的结果。链路层接口将系统级结果映射到物理层参数上去，有两种常用的方法：一种是链路级和系统级联合仿真，对系统信息进行实时的处理，
生产过程调度的数学模型
生产过程调度的数学模型
————————————————————————————————作者：————————————————————————————————日期: ?
生产过程调度的数学模型 陈丹妮 （韶关学院数学系９8数学本科班,广东韶关51200５） [摘要]:本文建立了生产过程调度的数学模型.利用运筹学和初等数学的相关知识,得出了相同资源 独立运作和相同资源可以通用两种情况下的无资源浪费、均衡生产的生产规模，相应周期和调度方案, 以及在资源限制条件下的最优调度方案. 关键词:数学模型；生产规模;周期；调度方案 １问题的提出 图1－1是某企业的生产示意图,A0是出厂产品，A1,Ａ2，…，Ａ６是中间产品，A i?→ ?k A j 表示生产一个单位Ａｊ产品需要消费k单位A i,其余类似. 图1-1 生产结构示意图 表1－1给出了生产单位产品所需的资源（工人，设备）和时间,注意表中所给数据是基 本的,即既不能通过增加工人和设备来缩短时间,也不能通过加长时间而节省工人和设备． 表1－1 生产单位产品所需的资源和时间 产品Ａ０A1 A2 A3 A4 A5 A6 需要的资源Ｉ类工人71 27 34 ３7 18 ３３１7 ＩI类工人 3 ２3 技术工人７9 0 7 6 5 11 甲类设备(台） 4 3 0 4 ２0 2 乙类设备(台) 1 ３ 1 0 2 ５６
加工时间(小时) 6 3 6 5 2 1 2 问题１无资源浪费、连续均衡生产的最小生产规模是多大?相应的最短周期是多少？ 其中“无资源浪费”指在整个生产周期中没有闲置的设备和闲散人员．“连续”指整个周期 中所有产品的生产过程不会停顿.“均衡”指所有中间产品Ａ1,…,Ａ6的库存与上一周期结束 时的库存相同.“生产规模”指完成整个生产过程所需各种资源的总和． 问题2 如果考虑相同的资源可以通用,那么问题1得到的最小生产规模在无资源浪费、 均衡生产中能否减少？请写出你得到的生产规模，相应的周期和生产过程的调度方案．问题3 如果该企业的资源限制为：I类工人１20名,IＩ类工人80名,技术工人25名,甲 种设备８台,乙种设备1０台及周期限制(一星期,共2４ 5.５=132ｈ)，请作出生产过程的 调度方案,使在均衡生产条件下资源的浪费最小．[1] 2 基本假设 假设生产开始的瞬间,马上有产品出产. 忽略各中间产品的输送时间． 资源(包括工人和设备）的效率是持续而且均衡的,即忽略工人的生理因素、设备的老化 损耗以及原材料的利用率对生产效率的影响. “数据是基本的”意思是一条生产线上安排操作的人员数经已经固定,如果人员减少了，流水线就无法生产,但如果人员多了,岗位并没有相应增加，因此不能加快生产的进度．[1]“均衡生产”是指经过一个周期的生产，中间产品供求平衡，其库存增加量完全转化组 装成为最终产品A0 ,其数值表示为零． “无资源浪费”是指各种设备和各类人员的拥有量与使用量相等,在整个生产周期中没 有闲置的设备和闲散的人员. “连续”是指在整个周期中，不仅资源的总使用量不变，而且用于各种产品的资源使用 量也不变，所有产品的生产过程不会停顿. ３问题的解决 3.1最小生产规模与最短生产周期 在生产各产品的资源均独立运作、不能通用的情况下,设生产单位产品所需的资源量为 １组，ｘｉ,i＝0,…,6,是生产各产品的组数，T为一个生产周期．由于生产是均衡的,在Ｔ 时间内生产的中间产品将全部组装成最终产品Ａ0.也就是说,周期时间内各中间产品的库存 增加量均为零，即中间产品的生产量与消耗量相等.现在要求最小的生产规模,也即要求各产 品的生产组数之和的最小值．由条件可以得出以下的线性规划模型[2]：
求解作业车间调度问题的全局邻域搜索方法
第15卷第7期计算机集成制造系统 Vol.15No.72009年7月 Computer Integrated Manufacturing Systems July 2009 文章编号:1006-5911(2009)07-1383-06 收稿日期:2008 06 18;修订日期:2008 10 13。Received 18June 2008;accepted 13Oct.2008. 基金项目:国家自然科学基金资助项目(70771008,70371057)。Fo undation item:Project supp orted by the National Natural Science Fundation, Ch ina(N o.70771008,70371057). 作者简介:崔健双(1971-),男,河北衡水人,北京科技大学经济管理学院副教授,博士,主要从事生产调度算法理论及应用、安全电子商务的研 究。E mail:cuijs@manag https://www.sodocs.net/doc/12531336.html, 。 求解作业车间调度问题的全局邻域搜索方法 崔健双,李铁克 (北京科技大学经济管理学院,北京 100083) 摘 要:采用传统的关键邻域搜索方法求解作业车间调度问题时,往往容易陷入局部极值而且难以跳出。为此,提出了一种具有动态调整能力的全局邻域交换策略,该策略有可能产生大量的不可行调度,需要一种筛选方法加以过滤。证明了一个新的邻域交换性质,利用该性质可以对所得调度方案作可行性约束判定,从而有效地过滤掉不可行调度。在此基础上,提出了一种求解作业车间调度问题的算法。最后,取不同规模的Benchmar k 问题算例对该算法进行测试,结果表明,无论从解的质量还是计算时间都取得了较好的效果。 关键词:邻域结构;关键路径;作业车间调度;邻域交换;调度算法中图分类号:T P18 文献标识码:A Global neighborhood algorithm for Job Shop scheduling problem CUI J ian shuang,LI T ie ke (Scho ol of Economic M anag ement,U niversit y of Science &T echno lo gy Beijing,Beijing 100083,China)Abstract:T r aditional cr itical neighbor ho od alg or ithms fo r Jo b Shop scheduling problem w ere easily t rapped into local optimal and hardly to escape.T o deal w ith t his pro blem,a g lo bal neig hbo rhoo d swapping st rateg y wit h dynamic adapatability w as pr oposed.H ow ever,this new strateg y mig ht possibly induce infeasible so lutio ns.T hus,a new pr oposition concerning the neig hbor hood sw apping str ategy w as presented and pr ov ed,w hich could be used to v erify whether a neighbor ho od swapping w as accept able or not.Based on this g lo bal neig hbo rhoo d st rateg y,a new alg o r ithm w as develo ped and tested by a gr oup of benchmark instances.T he r esults indicated that the new algo rithm ob tained satisfactor y results both on solut ions quality and computat ion time. Key words:neig hbo rhoo d structur e;crit ical path;Job Sho p scheduling ;neighborho od sw apping;scheduling alg o rithms 0 引言 自从20世纪50年代以来,调度问题相关理论及其应用技术的研究已经发展成为一门重要的学科,从经典的单机调度、并行机调度、车间调度发展到后来的多目标调度、随机调度和模糊调度等内容。调度问题成为从事运筹学、人工智能学和应用数学等学科领域的学者们关注的焦点,相应的应用领域在不断地扩大。随着问题研究的深化,人们对解决 调度问题的难度有了进一步的认识,发展了关于调度算法的有效性和计算复杂性理论,并且证明出许多调度问题包括多数作业车间调度问题(Jo b Shop Scheduling Problem,JSP)都是NP 完备问题[1]。JSP 是利用一组有限资源对一批有限任务在满足给定约束条件下求解最优目标函数的一个复杂的组合优化问题,也是迄今为止人们研究最多、研究成果最丰富、但仍未得到根本解决的问题之一。事实表明,有些NP 完备问题存在有限时间内的可行解,
生产调度建模
车间调度问题是指在工艺流程、机器设备、人力资源等约束的条件下对所加工工件顺序、资源分配做出合理安排，以使所求目标最优化。一个优秀的调度不仅能够保证车间作业计划的顺利实施，同时可以实现加工最大完成时间最小或者总生产费用最低等企业目标。 钢结构车间生产的产品型号较多，产品工序不尽相同，因此加工工艺流程也不完全相同，可将其划分为作业车间调度（job-shop schedule），但由于多道工序中并行机的存在，使其有别于传统的作业车间调度而表现出更加复杂的调度特点。理论上已经证明，作业车间调度问题（JSSP,Job Shop Scheduling Problems）是一个典型非确定性多项式困难问题，即NP-hard（Non-deterministic Polynomial-Hard）问题，是最困难的组合优化问题之一，而钢结构车间中并行机的存在则更加大了这一难度。 2.1 作业车间调度数学模型 在车间调度模型中，资源被称为机器，基本任务被称为作业，每件作业需要根据预先设定的工艺顺序安排一系列的零件的操作调度。经典车间调度问题研究n个零件在m台机器上加工次序的安排问题，而钢结构车间的调度研究在此基础上则同时包括研究工件的某道工序对并行机的选择。问题的已知条件为：各操作的加工时间和各零件在各机器上的加工次序约束，要求确定合理的加工开始时间和加工次序，实现加工性能指标的最优化，通常所选的性能指标有最小化最大完工时间，最小成本等，本模型选择最小化最大完工时间为性能指标。 为了问题的展开，对钢结构车间调度问题作如下标准性的假设： （1）一台机器在一个时间内只能加工一个零件； （2）每个零件的各工序利用每台机器不多于一次； （3）遵守工艺顺序，工序必须一次加工，后工序不能先与前工序 （4）一旦一个作业的加工开始，它必须加工完成； （5）一旦一个操作开始，它必须完成； （6）所有零件处于等待状态，在初始时刻都可以被加工 （7）每个作业独立的，也就是说不存在两个相同作业的操作同时发生； （8）设备调整时间是独立的，计算时被计入相对应机器加工时间内； （9）机器之间运输时间是独立的，同样被纳入后以机器加工时间； （10）作业数量是预先指定的； （11）机器数量是预先指定的 （12）机器上加工时间是预知且固定的； （13）机器不会发生故障中断并且总是可用的； 例如4个加工工序都为2次的工件在3台机器上加工顺序，其染色体编码如下： 染色体 2 4 3 1 1 2 3 4 3 1 2 2 3 3 1 2 染色体前半部分[ 2 4 3 1 1 2 3 4 ]为控制基因串，第一个2表示工件2的第一道工序，第二个2表示工件2的第二道工序，其余数字含义依次类推。前8位基因串表示4个作业共8个工序的加工顺序为工工件4工件3工件1工件1工件2 工件3工件4。染色体后半部分[ 2 1 3 3 2 2 1 3 ]为参数基因串，表示机器顺序依次为机器3机器1机器2机器2机器3机器3机器1机器2。 为了能够将染色体与实际问题相结合，需要对染色体进行解码，假设时间矩阵为： ；加工时间矩阵T ，T(i,j)表示工件i在机器j上的加工时间。 染色体需要通过解码才能表现出跟问题的直接关系，现用Uijkt来对此染色体解码。Uijkt即表示工件i的第j工序在机器m上的加工时间为t。解码如表3-1所示： 表31 染色体解码 基因 2 4 3 工序（2,1,3,2）（4,1,1,3）（3,1,2,3） 基因 1 1 2
车间生产管理方法
管理知识—车间生产管理方法 车间生产管理是对生产车间生产活动的计划、组织和监控，是和车间生产有关的各项管理工作的总称 A．生产管理过程组织 (1)生产过程步骤 包括生产技术准备过程、基本生产过程、辅助生产过程、生产服务过程。 (2)生产过程组织 在进行生产过程的时候，要求生产过程要*连续、*平行、*协调、有节奏，保证经济性。生产过程组织目的是在于合理*科学地安排生产计划，做到人力和物力都不会浪费。。从总体以上提高生产效率，减少生产周期，降低生产成本，更减少资金的占用，按期，保质，保量的完成生产计划。 B．车间生产计划编制 车间的生产计划编制是组织车间各项生产，完成生产任务，指导车间生产活动的重要工具。其工作内容有： (1)制定合理先进的质量及工作标准。 (2)制定班组和工作场地每月以内的生产作业计划。 (3)核算和平衡车间内部的生产能力。 (4)要对生产调度、进度管理、在制品管理、作业核算、生产作业统计及分析做好合理的控制。 (5)提出生产技术组织措施计划。 C．车间生产监控 车间生产监控，是对车间生产过程中执行作业计划时进行的监督，检查，调节和校正等工作。车间生产控制的主要工作有生产调度，作业核算和作业分析。 (1)生产调度 生产调度是根据车间生产计划的要求，对生产中各个环节的生产投入和生产进度进行检查，督促和协助的工作。。。。。做好调度的工作是完成车间作业计划的关键。调度工作要有健全的制度，包括值班制度、报告制度、会议制度、现场调度制度等。 (2)作业核算 包括产品及零件的出产量和投入量、完工进度、各环节完成的工作任务，生产人员以及设备的利用率等。 (3)作业分析 作业分析是在对生产控制的要求，记录，核算后的工作*总结，分析指标完成情况，进行信息反馈，使之作为生产活动和调度的依据。。。 D．成组技术的应用 成组技术也叫群组技术，是一种建立在以相似性原理为基础的合理组织生产技术准备和产品生产过程的方法。 成组技术即是对车间所有零件，按几何形状(轴、盘、箱体、齿轮等)、尺寸、加工方法(车、铣、刨、磨、钳等)、精度要求(普通、精密、高精)、毛坯种类(棒、板、管、铸件、锻件等)等分类系统进行零件的分类编码和划分零件组，用以准备生产和组织生产。成组技术的生产组织形式有： (1)成组工艺中心 组织一些结构相似的零件在某一设备上统一加工。 (2)成组生产单元 组织一组或几组工艺相似的零件进行统一的工艺路线配备和布置设备。
炼钢物流调度仿真模型分析
炼钢物流调度仿真模型分析 【摘要】生产调度系统是炼钢车间制造执行系统中的重要组成部分，它根据供应(炼钢)的状况和交付(热轧)的需求，控制冶炼、精炼和连铸作业工序的生产节奏，使工序间的物流传递满足生产工艺要求，确保生产的顺利进行。本文分析炼钢车间生产调度系统的外部环境，运用面向对象技术建立炼钢生产物流调度仿真对象模型。 【关键词】炼钢；调度；面向对象；仿真 1钢铁生产工艺流程介绍及分析 现代钢铁生产流程较为复杂，涉及的工序很多，一个典型钢铁企业的生产流程可以分为三大部分:炼铁（Iron Making)区域、主炼钢(Primary Steelmaking)区域和精整加工(Finishing)区域，其中主炼钢区域包括炼钢、连铸、热轧等工序，精整加工区域包括冷轧、镀涂等工序 2炼钢生产系统结构分析 2.1系统静态结构 图1表现的系统结构模型通过类与类之间的关系反映出系统的基本框架。图1中，我们根据炼钢车间生产调度系统作用和其外部环境的特点，抽象出作业计划、生产调度和物料跟踪3个核心类。 （1）作业计划类接受生产订单并将其分解为任务单元、平衡设备能力、指派加工设备、编制浇次计划和炉次计划。与其相关联的实体有工具、原料、设备、工艺路线以及匹配规则等。 图1炼钢车间生产调度系统类图 （2）生产调度类解决设备资源占用冲突，确保物流状况符合作业计划的要求，根据生产实绩数据及时更新相关状态。它包括资源协调、设备匹配和问题识别等3个子类，分别对应于生产调度系统中的资源状况竹理、炉次设备指派、动态调整等3个方面的功能。 （3）物料跟踪类从过程控制系统或人机交互系统采集生产实绩数据，进行显示和分析整理，并向生产调度模块提供所需的生产实绩数据。 2.2系统动态结构
基于Flexsim的车间调度优化
收稿日期:2009-06-13;修回日期:2009-09-01 基金项目:国家863计划资助项目(2007AA04Z112);国家自然科学基金资助项目(50875046) 作者简介:余晓光(1984-),男,江苏南京人,硕士研究生,研究方向为车间生产计划调度与仿真;严洪森,教授,博士生导师,研究方向为生产计划与调度、知识化制造、并行工程等。 基于F lexsim 的车间调度优化 余晓光,严洪森,殷乾坤 (东南大学复杂工程系统测量与控制教育部重点实验室,江苏南京210096; 东南大学自动化学院,江苏南京210096) 摘 要:基于三维动画仿真软件Flexsim ,文中对航空附件加工车间这种多品种、小批量生产的作业车间(Job -Sho p )进行了调度优化研究。介绍了Flexsim 连接数据库的技术与遗传算法求解生产调度的方法;在Flexsim 中建立虚拟生产车间模型,并且在Flexsim 虚拟车间模型内部嵌入C ++数据库操纵程序,将仿真模型与生产管理数据库连接,使模型可以实时采集生产数据;最后通过实例说明Flexsim 仿真与调度优化相结合的方法可以有效地提高航空附件加工车间的效益,证明了方法的有效性。 关键词:Flexsim ;遗传算法;作业车间调度;数据库连接 中图分类号:TP391.9 文献标识码:A 文章编号:1673-629X (2010)03-0044-04 Workshops Scheduling Optimization B ased on Flexsim Simulation YU Xiao 2guang ,YAN Hong 2sen ,YIN Qian 2kun (Ministry of Education K ey Lab.of Measurement and Control of CSE ,S outheast Univ., Nanjing 210096,China ; School of Automation ,S outheast Univ.,Nanjing 210096,China ) Abstract :On the basis of Flexsim simulation ,this paper studies aircraft accessory job -shop scheduling optimization problems ,which is multi -categories and small batch.First of all ,the Flexsim database link method and genetic algorithm in job -shop scheduling are intro 2duced.And then ,the virtual workshop model is built in Flexsim environment ,and embedded by database operation C ++program which could access production management database.The virtual workshop could update data from manufacturing database in real time.In the end ,the simulation example confirms the method of Flexsim simulation in conjunction with scheduling optimization can improve the workshop ’s benefit ,and is effective. K ey w ords :Flexsim ;genetic algorithm ;job -shop scheduling ;database link 0 引 言 现代生产车间中为了适应多变的需求,逐渐形成了多品种、小批量的生产方式。在多品种、小批量的生产方式下选择合适的生产调度策略显得尤为重要[1]。采用合适的生产调度可以提高机器的利用率,平衡各生产工位负荷,保证按时按需生产。 遗传算法是一种解决生产调度问题的有效算法,文献[2]使用的G ASA 混合策略求解Job -Shop 调度问题和文献[3]使用的自适应遗传算法解决作业车间 调度问题都取得了良好的效果。 Flexsim 是一种面向对象的可视化3D 仿真软件, 可以方便地建立生产线模型并通过仿真进行效能评价[4],文献[5]采用Flexsim 对冲压车间进行了调度优化,并介绍了Flexsim 调用Excel 进行数据交换的方法,但未实现Flexsim 调用数据库,进行与数据库的实时数据交换。文献[6]采取计划与调度同时优化的方法首先建立粗生产计划并在粗生产计划的基础上求解调度,并成功应用于汽车装配车间。但是求解速度较慢,并且采用文字界面,没有建立可视化的车间模型。而文中的研究对象是航空附件生产车间,由于其产品的特殊性必须按订单生产。因此首先在约束(订单需求和机器可利用时间)下使用遗传算法求解最优调度;然后在Flexsim 中建立3D 虚拟车间模型,并通过该模型访问生产管理数据库获得虚拟车间的调度与工时数据;最后通过仿真对方案进行比较。 第20卷 第3期2010年3月 计算机技术与发展COMPU TER TECHNOLO GY AND DEV ELOPMEN T Vol.20 No.3Mar. 2010