基于多Agent的JobShop调度方法研究
基于多Agent 的Job Shop 调度方法研究
饶运清 教授
饶运清 谢 畅 李淑霞
华中科技大学机械科学与工程学院,武汉,430074
摘要:针对Job Shop 调度问题,提出基于多Agent 的车间调度模型,实现调度甘特图的自动生成。在此基础上,设计了多Agent 分组协作机制;实现了多目标优化调度,提高了调度优化算法的实用性和优化效果;分析了车间调度中各类干扰因素的特点,实现动态调度,提高了系统的适应性和健壮性。最后给出了实例验证。
关键词:作业调度;动态调度;代理;多Agent 系统中图分类号:TH166;TP278 文章编号:1004—132Ⅹ(2004)10—0873—05
R esearch on Multi -Agent -B ased Scheduling Approach for Job Shop Scheduling
Rao Yunqing Xie Chang Li Shuxia
Huazhong University of Science and Technology ,Wuhan ,430074
Abstract :To solve the problem of Job -Shop scheduling ,a scheduling framework based on multi -a 2gent system was developed ,which can create scheduling G antt Chart automatically.Under this frame 2work ,a grouping cooperation mechanism among multi -agents was designed so as to achieve multi -objec 2tive for job -shop scheduling and to improve the practicability and effectiveness of optimization algorithms.Meanwhile ,the characteristics of various disturbances in job -shop scheduling was analyzed ,based on which ,the mechanism of dynamic scheduling was achieved.In this way ,the flexibility and robus 2ticity of the scheduling system is enhanced.Finally ,a case study was provided to validate the proposed scheduling approach.
K ey w ords :Job Shop scheduling ;dynamic scheduling ;Agent ;multi -agent system
收稿日期:2003—09—01
基金项目:国家自然科学基金资助项目(50105006)
0 引言
高效、实用的调度方法和优化技术是实现车间生产高效率的关键。实际的车间调度问题主要体现在复杂性、动态随机性和多目标性等方面[1]。车间调度问题的研究最初集中在整数规划、仿真[2]和规则调度[3]等方法上,这些方法不是调度结果不理想,就是难以解决复杂的问题。近年来,在车间调度领域也出现了许多新的优化方法,如神经网络[4]、模拟退火法、遗传算法[5,6]等智能计算方法,使得车间调度问题的研究方法向多元化方向发展。其中,多Agent 系统(multi -agent system ,MAS )由于具有分布式并行处理、
健壮性、可伸缩性、可维护性等特点,已成为研究的前沿和热点[7]。
本文针对Job Shop 调度问题的特点,提出了一种基于多Agent 的车间调度方法,运用多Agent 技术对车间的生产调度过程建模,用设备Agent 仿真并实时监控加工设备的运行,用工序Agent 管理工序的调度过程。
1 基于MAS 的调度模型
1.1 问题描述
假设如下一般情况成立:
(1)原材料、辅料、备品备件及其他资源充足,不在调度之列;
(2)每道工序加工只需要一种加工设备;
(3)任务的加工时间是确定的,包括安装时
间、拆卸时间等;
(4)忽略刀具、工装、托盘等对象,只考虑工件流的调度;
(5)调度安排到工序,即确定工序的加工机床、加工开始时间。
则车间调度问题是指在满足以下约束条件的情况下,确定每道工序的加工设备和开工时间:
(1)时间约束 包括任务的释放期约束及任务的交货期约束,即加工任务第一道工序的开工时间不能早于任务的释放期,最后一道工序的完工时间不能晚于任务的交货期。(2)顺序约束 除第一道工序外,任何其他工序的开工时间不能早于上道工序的完工时间。(3)能力约束 一台加工设备在任一时刻只
?
378?
能加工一道工序。1.2 基于MAS 的车间调度模型
本调度系统主要由设备Agent (DA )和工序Agent (PA )组成,见图1。PA 与DA ,PA 与PA 之间可以通信。PA 可以自主地在DA 的时间轴上选择合适的位置,将工序安排到该处,形成生产调度甘特图,实现调度功能
。
图1 基于MAS 的车间调度模型
1.2.1 设备Agent
设备Agent 是车间中加工设备的代理。每个设备Agent 对应一台加工设备,并通过设备接口与该加工设备相连接。通过设备接口,设备Agent 能获取加工设备的技术参数和设备状态等信息,并能将加工任务发送到加工设备。设备Agent 可定义为一个三元组
M =
式中,M id 为设备Agent 的唯一标识;σ为设备Agent 的属性、状态、所具有的信息特征;α为作用于该Agent 的一组操作,描述其具有的行为。
Agent 可分为智能型的认知式Agent 和非智
能型的反应式Agent 。设备Agent 的主要作用是动态标定自身状态,并激发其他Agent 的进程,它本身不具有判断、推理能力。因此,将设备Agent 设计成非智能型的反应式Agent ,其内部结构见图2
。
图2 设备Agent 结构
1.2.2 工序Agent
工序Agent 由系统根据到达的任务动态生
成,每个工序Agent 对应一道工序,它管理该工序的相关数据和生产调度过程;当某一工序的加工任务完成时,与其对应的工序Agent 将被撤销,生产调度过程中形成的数据存入日志数据库。工序Agent 可定义为一个三元组
P =
式中,P id 为工序Agent 的唯一标识;ω为工序Agent 的属
性、状态、具有的信息特征;δ为作用于该Agent 的一组操作,描述其具有的行为。
工序Agent 在调度过程中起着重要的作用。它与DA 及其他PA 协作,根据所获得的信息和优化目标为工序搜索合适的加工设备和开工时间,并且在生产过程受到干扰的情况下,进行动态调度。工序Agent 属于智能型的认知式Agent ,具有判断、推理能力,其内部结构见图3
。
图3 工序Agent 结构
1.2.3 Agent 间的协作模型
通信与协作是多Agent 系统运作的基础。从以上Agent 模型可以看出,各Agent 的数据和行为是通过与其他Agent 的通信与协作起作用的。本系统中存在两类协作关系:
(1)PA 与DA 间的协作 PA 与DA 是不同类型的Agent ,属于异质Agent 。它们之间的协作主要有三方面(见图4)。首先,DA 的数据库中记录着待加工工序的开工时间和完工时间,这些数据是PA 进行调度的依据,同时也是调度的结果,所以PA 要向DA 查询数据并写入调度结果。其图4 PA 与DA 间的
协作模型
次,DA 是反应式Agent ,不参
与调度的逻辑推理过程,只是简单地响应PA 的请求。另外,DA 还监控设备的运行状况,将出现的意外情况及时地
通知PA ,以便进行动态调度。(2)PA 与PA 间的协作 由于各PA 的内部结构相同,图5 PA 间双向对称的协作关系并且在系统中的地位也相同,因此PA 之间的协作属于同质Agent 之间的协作,
而且是双向对称的(见图5)。又由于每个PA 只管理某一道工序的数据,数据
量少且数据结构统一,所以PA 间的协作可以设计成简单统一的模式,从而极大地降低系统的复杂程度。PA 与PA 间的协作关系见图6,其中调度信息包括调度结果和中间信息。
2 调度方法
车间生产过程复杂多变,要求调度系统具有高度的适应性和自治性,以保证车间生产能够持
?
478?
图6 PA 与PA 间的协作模型续优化地进行。2.1 约束维护
车间调度要满足一定的约束条件,包括时间约束、顺序
约束、能力约束等。
这是保证车间调度
系统正常运行的最基本要求。因此,PA 的调度过程按以下步骤进行:
(1)确定PA 的最早开工时间t s ,使其不早于
任何前向工序的完工时间和工件释放期;
(2)确定PA 的最晚完工时间t e ,使其不晚于任何后向工序的开工时间和工件交货期;
(3)向DA 查询加工设备从t s 到t e 之间的不小于PA 加工时间u 的空闲时间段集T ;
(4)在T 中确定合适的开工时间。这样就使车间调度的约束条件都能得到满足。2.
2 多目标优化
实际的生产调度往往是多目标的。不同的加工任务对调度有不同的要求,如急件任务要求完工时间尽可能早;大批量零件要求降低库存和在制品数量,以减少对资金的占用等。另外,车间生
产管理也对调度过程有一定的要求,如设备利用率,负荷均衡等。传统的单一优化算法往往不是顾此失彼,就是效果不理想。
针对这一情况,笔者将多种优化算法嵌入到PA 的知识库中,并综合分析了它们各自的特点和适用场合,见表1。
表1 各种车间调度优化方法的特点及其适用场合
算法名称运算速度优化效果调度规模适用场合整数规划慢好小小规模
启发式搜索中较好中广泛规则调度快差大,中,小快速调度遗传算法中较好中广泛招投标方法
较快
中
大、中
大规模
在调度的过程中,若发生资源(加工设备)冲突,PA 按照分组协作、组内优化的方式处理:首先,PA 根据冲突的范围(加工设备、工件数、工序数)和特点,形成一个或多个PA 集团(PA group ,PAG );然后,PAG 根据情况(调度规模、优化目标),从知识库中选取合适的优化算法,对PAG 内的工序进行优化调度(具体方法见实例分析)。这样不仅兼顾了各PAG 的优化目标,而且将优化算法的运算限定在最小、最适用的范围内进行,提高了算法的优化效果,减少了运算时间(见图7)。
图7 基于MAS 的多目标优化
2.3 动态调度由于生产过程中存在许多干扰因素,如设备故障、急件、误工等。为了实现动态调度,首先要对干扰因素进行分类。按干扰的来源可如下划分:
(1)设备干扰 即由于加工设备的原因产生的干扰,如设备故障、误工等;(2)任务干扰 即由于加工任务的变更而产生的干扰,如急件订单、取消订单等。
对于设备干扰,可以由DA 进行监控。当干扰出现时,DA 激活受到影响的PA ,进行动态调度;对于任务干扰,即当PA 发生变更(新增、取消、变化)时,由发生变更的PA 激活受到影响的
PA ,进行动态调度。
另外,按干扰的影响程度可如下划分:
(1)约束干扰 使调度的约束条件不能完全满足的干扰,如关键设备损坏;(2)优化干扰 必须重新进行调度,才能完全满足约束条件的干扰;(3)无损干扰 对约束和优化效果没有影响的干扰;
(4)有益干扰 如新增设备,任务取消等。
对于不同程度的干扰,可以采用不同的处理方式。如对于约束干扰,进行动态调度的同时,需要发出警告;而对有益干扰,可以处理也可以不处理。
?
578?
3 实例分析
下面通过一个实例来具体说明上述调度方法的应用。现有一个4×4的Job Shop调度问题,有关数据见表2。
表2 4×4型Job Shop调度问题
工件释放期交货期优化目标(工序,设备,工时) 108完工日期(1,1,3)(2,2,1)(3,3,1)
2110完工日期(1,2,3)(2,3,1)(3,4,1)
3212减少库存(1,4,2)(2,2,2)(3,3,1)
4213减少库存(1,4,3)(2,3,2)
3.1 生成工序Agent
首先根据一定条件(如交货期)确定所有工件的优先级,按优先级的高低顺序生成工序Agent。这里,按工件1、工件2、工件3、工件4的顺序进行,结果见图8。值得说明的是,根据优化目标不同,工件内各工序Agent的生成顺序,亦会有所不同。如工件1、工件2顺排,即各工序按工件释放期由前向后排;工件3、工件4倒排,各工序按工件交货期由后向前排。
图8 工序Agent的生成
3.2 多目标优化
上述过程完成后,系统只能满足车间调度的约束条件,并没有达到优化。有些任务可能还存在着超期现象。此时系统中存在3处资源冲突: PA1.2和PA2.1的资源冲突、PA3.3和PA4.2的资源冲突、PA2.3、PA4.1和PA3.1的资源冲突。
根据分组协作、组内优化的处理方式,采取如下步骤:
(1)将存在资源冲突的PA组成PA G,并根据PA间的关系(见图9)列表(见表3)(a i,j>0表示i对j有影响)。
(2)将联系比较紧密的PA合并到同一个PA G中。如表3中,PA1.3只受(PA1.2,PA2.1)的影响,合并后得到表4
图9 PA G的形成
表3 PA关系
PA1.1
PA1.2
PA2.1
PA3.2PA1.3PA2.2
PA4.2
PA3.3
PA4.1
PA3.1
PA2.3 PA1.11
PA1.2
PA2.1
111
PA3.21
PA1.31
PA2.211
PA4.2
PA3.3
11
PA4.1
PA3.1
PA2.3
表4 合并PA1.3
PA1.1
PA1.2
PA1.3
PA2.1
PA3.2PA2.2
PA4.2
PA3.3
PA4.1
PA3.1
PA2.3 PA1.11
PA1.2
PA1.3
PA2.1
12
PA3.21
PA2.211
PA4.2
PA3.3
11
PA4.1
PA3.1
PA2.3
(3)重复步骤(2),直到所有受PA G影响的PA都被合并,形成了3个PA G(见表5、图9)。
表5 合并PA
PA1.1,PA1.2,
PA1.3,
PA2.1,PA2.2
PA3.2,
PA3.3,
PA4.2
PA2.3,
PA3.1,
PA4.1
PA1.1,PA1.2,
PA1.3,
PA2.1,PA2.2
21 PA3.2,
PA3.3,
PA4.2
2 PA2.3,
PA3.1,
PA4.1
(4)PA G间的合并。PA G2和PA G3的联系
?
6
7
8
?
比较紧密,而且规模都不是很大,在时间允许的情况下,可以将它们合并生成PA G 4,得到表5。
表5 合并PA G
PA1.1,PA1.2,
PA1.3,PA2.1,PA2.2
PA2.3,PA3.1,PA3.2,PA3.3,PA4.1,PA4.2
PA1.1,PA1.2,
PA1.3,PA2.1,PA2.23
PA2.3,PA3.1,PA3.2,PA3.3,PA4.1,PA4.2
(5)对PA G 进行优化调度。由于PA G 1对PA G 4有影响,因此应先对PA G 1进行优化调度(若两个
PA G 是相互独立的,则它们的优化调度可以同时进行)。
(6)选择调度算法。由于PA G 1的规模较
小,参照表1,可以从知识库中选择整数规划调度
算法。
(7)将PA G 1中各PA 的工序数据,代入到整数规划调度算法模块中,进行运算。
(8)PA G 1中的PA 根据运算结果完成PA G 1的优化调度。
同样,PA G 4经过类似的步骤完成优化调度。优化调度的结果见图10。
图10 多目标优化调度结果
需要指出的是,PA G 的形成并不是一成不变
的。如在上例中,可以将PA G 1、PA G 2和PA G 3合并成一个PA G ,对其进行全局优化,但这样就增大了调度的规模,需要更长的运算时间;另一方面,也可以分别对PA G 1、PA G 2和PA G 3进行优化调度,虽然达不到全局优化的效果,但是速度快,特别适合于动态调度这类需要快速响应的场合。3.3 动态调度
多目标优化调度完成后,DA 将到达的任务通过设备接口发送到对应的加工设备去执行,并实时监控任务的加工进度。现假定DA1监测到PA1.1将误工2h ,DA1通知PA1.1。PA1.1根据所受干扰的情况,将完工时间延长至时刻5,然后
向受到影响PA1.2发送消息。PA1.2调整开工
时间至时刻5,以满足车间调度的约束条件。同样地,PA1.3将开工时间调整至时刻6(见图11)。这样,所有受到影响的PA 的动态调度都已完成。若此时有新的资源冲突产生,可再进行多目标优化调度。
图11 动态调度
4 结论
本文提出的基于多Agent 的Job Shop 调度系统结构简单、方法灵活、可扩充性强,能有效控制调度规模,充分发挥各类调度优化算法的效果;同时具有智能性、自治性、适应性和健壮性等特点,特别适用于复杂的车间调度环境,应用前景十分广阔。
参考文献:
[1] 熊锐,吴澄.车间调度问题的技术现状与发展趋势.
清华大学学报,1998,38(10):55～60
[2] 方剑,席裕庚.基于事件驱动的Job Shop 仿真调度
系统.系统仿真学报,1997,9(4):42～61
[2] Panwalkar S.A Survey of Scheduling Rules.Opera 2
tion Research ,1977,25(1):45～61
[4] 彭观,陈统坚,欧阳惠芳.基于神经网络的FMS 动
态调度决策.华南理工大学学报,1998,26(6):60～
64
[5] 徐跃飞,李言,张晓坤,等.遗传调度算法的研究.
中国机械工程,1998,9(3):56～60
[6] 顾擎明,曹丽娟,宋文忠.解Job Shop 调度问题的自
适应遗传方法.控制与决策,1998,13(5):589～593
[7] 乔兵,朱剑英.多Agent 智能制造系统研究综述.南
京航空航天大学学报,2001,33(1):1～7
(编辑 郭 伟)
作者简介:饶运清,男,1968年生。华中科技大学机械科学与工程学院教授。研究方向为计算机集成制造、车间生产管理与控制。谢 畅,男,1977年生。华中科技大学机械科学与工程学院硕士研究生。李淑霞,女,1975年生。华中科技大学机械科学与工程学院博士研究生。
?
778?
电网经济调度方法研究与应用
电网经济调度方法研究与应用 发表时间：2019-09-11T09:45:53.767Z 来源：《中国电业》2019年第10期作者：沈宗宝 [导读] 电能因具有瞬时性而难以保存，但作为现代工业社会的支柱性能源，必须对其进行有效调度，才能较好地加以利用。 四川西昌电力股份有限公司四川省 615000 摘要：电能因具有瞬时性而难以保存，但作为现代工业社会的支柱性能源，必须对其进行有效调度，才能较好地加以利用。 关键词：电网经济；调度方法；研究；应用 1电网经济调度概述 1.1基本概念 电网经济调度是根据电网运行的基本原理，在保证安全、可靠运行和满足用电需要、电能质量的前提下，通过调整电网运行方式，制定各站(厂)或线路之间的最优负荷分配方案等多种技术方法和管理手段，对电网资源进行优化配置，以降低运行成本。近年来，随着用电量的逐年增加，电力系统也在快速发展。在保障电网安全、稳定运行的条件下，增强电网的经济运行能力，即是调度运行人员的重要工作，也是电力企业经营行为的关键内容。 1.2经济调度一般采取的措施 1.2.1根据电网传输需要，采取实时经济调度在保证电力供应量与实际相符的情况下，调度部门应尽可能降低能量损失，提高电网的经济性，如在用电低谷时期减少电网的电力供应量，在用电高峰时期增加电网的电力供应量。 1.2.2根据电网运行状况，采取运转备用调度在满足电力传输高峰要求的情况下，主要选用运转备用调度的形式增强电网的经济性。在保证电力线路正常运行、维护、维修的同时，适时关闭某些电力线路，可以减少电网自身产生的损失。 1.2.3根据对环境的污染状况，采取环境保护调度在生产及传输电能的过程中，为了减少其对环境的污染，需要参考电网的实际污染状况进行环境保护调度，以增强电网的经济性，同时降低电能损失。 1.2.4根据电网负荷状况，采取稳定约束调度在确保电网安全运转的条件下，需要根据电网的负荷情况，对电网进行负荷预测和安全控制。可采取安全约束调度的方式，减小电网负荷，降低电能损失，提高电网的经济性。 1.3存在的问题 随着电力工业的发展，手工管理方式已不再适应电力生产的需要，信息的收集、存储、传输、查询、加工及决策等工作量越来越大。这就要求我们必须提高管理水平，通过建立计算机信息系统，改变原有的管理方式、体制和手段，以增加经济和社会效益。因此，安康供电分公司充分利用现有的PAS高级应用软件，研究开发了经济调度软件系统。 2PAS高级应用简介 PAS高级应用软件利用电网的各类实时数据进行在线分析，如开关状态、有功功率、无功功率等信息，辅助调度员通过制定最优的电网运行方式。安康供电分公司PAS高级应用软件是东方电子有限公司开发的系统，主要由调度员潮流、状态估计、网络拓扑和负荷预测四部分组成。 2.1网络拓扑 网络拓扑是PAS高级应用软件中的最基本功能，主要用于网络分析。它根据电网的遥信信息和多种元件的关系，确定地区电网的电气连接状态，产生调度员处理数据所需要的网络模型。为了保证计算结果的正确性，必须使所建的模型和实际的运行方式相一致。 2.2状态估计 状态估计是调度员潮流功能的基础。利用SCADA实时遥测遥信数据进行计算、分析和校验，可辩识出不良数据。不但能估计开关的功率、母线电压等，而且能计算出某些无法量测的电气量，对准确的运行方式。最终得到一个完整且相对准确的运行方式。自动化运维人员根据状态估计提供的可疑数据功能，能及时发现并处理系统缺陷。调度运行值班人员则通过状态估计掌握电网的实时运行状态，如电网运行方式、潮流分布等。 2.3调度员潮流 这是PAS高级应用最基本的应用之一。调度员潮流既可以对电网当前的运行状态进行分析，也可以对历史和未来的运行方式进行分析，还可以用来校核调度计划的安全性和合理性。调度员潮流能得到电网的实时运行状态。首先利用SCADA实时数据和提前设定的计算条件进行数据初始化；网络拓扑根据系统的遥信信息确定电网的电气连接状态；状态估计经过一系列的专业计算剔除其中的坏数据，最后建立研究态。 2.4负荷预测 人工预测主要根据前几日的负荷或历史同期数据进行分析预测。工作既繁琐又复杂，结果还不理想。负荷预测能够根据历史数据，预报未来的电网负荷，通过分析预测值与实际值之间的误差，自动修正预测模型的参数。该软件的应用节省了大量人工预测时间，能根据历史数据预测未来一至多天的负荷，还能从多种角度自动检测不正常的历史数据，并对坏数据进行报警。 3经济调度软件功能分析 针对安康网内小水电资源丰富的特点安康供电分公司研究开发的经济调度软件，对系统内小水电、变电站的运行状况进行实时监测和分析，为辅助调度员经济、科学、合理调度，最大限度实现电网安全、优质、经济运行。 3.1电置统计分析模块 从SCADA系统获取联络线有功功率、无功功率、当日电量、小水电有功功率等实时数据；从关系数据库中读取各个联络线的月／年累积电量等。然后，人工输入联络线的月／年关口交易计划电量、水电站月／年发电计划电量等。此模块利用SCADA提供的用户控制语言编程实现。 3.2有功功率实时平衡模块 监视联络线断面的实时有功功率。当超过人工设置的限额时，采用特定分配算法，将超限差值自动分配到相关的各个水电站中，以报警提示的方式告知调度人员。(1)采用网络拓扑、潮流计算和灵敏度分析算法，按照水电站当前发电功率等比例分配，将差值功率分配到灵敏度较高的各个水电站中。此算法比较精确，但条件苛刻，要求网络拓扑、潮流计算等模块正常运行，需要加强PAS软件的日常维护工作。
数学建模--车间作业调度问题
一、二维背包问题 一维背包问题讨论的背包问题只有一种限制，即旅行者所能承受的背包的重量（亦即重量不能超过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）
城市公共自行车调度方法研究
城市公共自行车调度方法研究 随着社会经济的不断发展,人们的交通出行需求越来越大,城市交通问题也越来越严重。面对这样的形势,低能耗、低排放、低污染的绿色交通理念被越来越多的人认同。 公共自行车在缓解交通拥堵,解决出行“最后一公里”问题方面具有突出优势。但是由于公共自行车站点规划布局的不合理,以及运营管理部门对公共自行车系统的调度不合理等原因,在公共自行车系统运行过程中经常出现“无车可借,无桩位可还”的问题,这种现象制约着城市绿色交通的有序发展。 基于这种现象,本文对城市公共自行车运营调度问题进行了研究。首先,本文在总结归纳国内外现有研究成果的基础上,阐述了城市公共自行车的使用特征,并分析了公共自行车调度的必要性。 同时,对公共自行车调度系统的调度内容、调度模式、调度成本等进行了深入分析。在调度模式方面,分析了传统多车场简单分区调度模式的特点以及存在的不足,提出了多调度车场协同运输的调度模式。 其次,分析了多车场协同运输调度模式的特点以及需要考虑的因素,在此基础上构建了一个以综合调度运输成本最低的多车场协同调度模型。该模型将系统内所有调度车场进行协同考虑,优化公共自行车静态调度的最优路径问题。 在模型求解方面,本文通过对不同启发式算法适用性的分析,最终构造了一种融合遗传算法和禁忌搜索算法的启发式算法,并通过Matlab软件编程实现模型的求解。最后,以中山市公共自行车租赁系统为例,分别采用多车场协同运输调度模式和传统多车场简单分区调度模式进行调度。 以综合调度成本最低为目标,对两种调度模式下的最优调度方案进行对比分
析,验证了本文所构建的多车场协同运输的调度模型以及求解算法的适用性。
多Agent系统理论概述
多Agent系统理论概述 摘要：Agent在AI(AI:Artificial Intelligence)研究领域已经成为热点，Agent 技术提供了一种新的计算和问题求解规范。本文简要的讨论Agent、多Agent系统。 关键词：多Agent系统概述 1Agent概述 1.1Agent的基本概念 Agent的概念最早出现在20世纪70年代的人工智能中，80年代后期，被译为“代”理，“智能体”或“智能主体”。这些概念在许多领域被引用，不同的研究领域和内容，给出了许多不尽相同的定义。目前为止还没有一个对Agent统一的定义，但多数研究者接受wooldridge和Jelinings所提出的Agent定义，即Agent 是一个具有自治性、社会能力和反应特性的计算机软、硬件系统，它具有自治性、社会能力、反应性和主动性。 1.2Agent具有的特性 根据wooldridge的定义，对于Agent所应具有以下特征： 1.自治性(Autonomy)：Agent一般都具有自己的资源和局部于自身的控制机制，能够在没有外界直接操控下，根据自身的内部状态以及感知的外部环境信息，决定和控制自身的行为。 2.社会能力(Social Ability)：Agent之间并不是孤立的。和人一样，Agent具有通信能力，能够通过某种Agent通信语言与其他Agent进行各种各样的交互，也能和其他各类Agent一起有效地完成各种层次的协同工作。 3.反应性(Reactivity)：Agent能够及时地感知其所在外部环境的变化，并能够针对一些特定的时间做出相应的反应。 4.主动性(activity)：Agent能够遵循其承诺采取主动行动，表现出面向目标的行为。它要求Agent保持比较稳定的目标，它的动作都是以此目标为依据的，从而产生一种叫做目标指引的行为(Goal Directed Behavior)。 1.3Agent分类 从不同的角度，Agent有下面几种分类方法： 1.根据Agent的存在形式：分为有形Agent和无形Agent。有形Agent以是智能控制器、机器人，甚至是操作人员。无形Agent一般指软件Agent，可能有
作业车间调度模型
基于WSA算法的作业车间低碳调度方法研究 1.1 引言 本章主要研究了以最大化完工时间和能耗指标为目标的作业车间低碳调度模型的求解方法。首先，建立了多目标作业车间低碳调度模型；然后基于Pareto 支配理论，设计了一种高效的MODWSA算法获得满意的Pareto非支配解；最后，设计了一套测试算例，将MODWSA算法与其它经典多目标算法进行比较分析，验证了MODWSA算法的优越性。在本研究中，作者完成了两项工作：首先，构建了一个新的多目标作业车间低碳数学模型；其次，设计了一种高效的MODWSA算法获得满意的Pareto非支配解。 1.2 作业车间低碳调度模型 本章研究的作业车间低碳调度问题可描述如下：对给定的n个工件及k台机器，一个工件的加工需要经过m道工序，每道工序允许在特定的机器上加工，任意一台机器在任意一个时刻仅能加工某一工件的某一道工序，并且一个工件只能在其上道工序完成后下一道工序才能开始加工[插入文献]。 考虑机器的准备时间，准备时间与同一机器上相邻两工件的加工顺序相关，并且机器的启动和工件的加工是相连的。对应于不同工序，机器具有不同的速率档位进行加工，并且可以进行调节。从能耗的角度来看，机器有四种不同的状态：加工状态(机器在加工工件)，启动状态（机器在准备加工一个新的工件），待机状态（机器处于空转中），以及关机状态（机器被关机）。通常情况下，当机器在较高速率运作时，工件的加工时间会被缩短，但是相应的能耗会增加。因此本问题以最大化完工时间和能耗指标为目标，由于本章所研究问题的特点，该问题要比传统的作业车间调度问题要复杂的多。在该问题中，其它设定如下： ●工件在车间里被连续加工。也就是说，加工过程不能被中断。 ●机器允许有空闲时间，并且各阶段间具有容量无限的缓冲区。 ●当有第一个工件在机器上加工时，机器开机；当在该机器上加工的所有工件 加工完毕后，机器关机。 ●机器速度在工件加工过程中不能进行调整。 1.2.1 混合整数规划模型 为了提出问题的数学模型，根据上面对问题的描述，我们首先定义了下面的相关数学符号。
多核处理器调度方法研究
多核处理器调度方法研究 【摘要】在多核处理器蓬勃发展的今天，温度过高成为制约其性能和稳定的关键因素。本文首先在单核处理器上，以热传递理论为基础，以温度与时间的一个简明等式详细分析了任务组的各种排列方式对单核处理器的峰值温度可能造成的影响，并提出了简单易行免于复杂计算的调度方法；然后将该方法拓展到多核处理器环境，通过合理分配、核上调度和核间迁移，达到了降低各核峰值温度的目的。 【关键词】多核；温度感知；调度；热传递 0.引言 多核处理器是当前及未来处理器发展的主要趋势。单个处理器中集成的核的数量已经由两个发展到四个、八个甚至更多。核的数量的增多提高了处理器的计算能力，但也带来了处理器功耗过大和温度过高的问题。有一些研究致力于减少多核处理器的功耗，而另一些研究则着眼于解决温度过高的问题。功耗问题和温度问题并不完全相同，两个处理器的功耗总量相同时温度的变化曲线却不一定相同。减耗的直接目的是节能，通过减耗有可能间接实现降温的目的，但不能保证没有温度过高的时刻。一个过高的温度会直接导致处理器性能降低及故障率升高，所以相对而言，降低温度比减少功耗有更为重要的意义。本文着眼于解决峰值温度过高的问题。 为了解决这一问题，在硬件上一般常采用动态电压调节(DVS)和clock gating 等技术。DVS适时地降低电压与频率以减少功耗，clock gating当温度达到某个阈值时暂时停止指令的执行。这两种方法尤其是后者严重牺牲了处理器性能，只能在必要时刻合理使用。国内外也有一些文献提出软件方法，但往往没有与温度直接相关的模型，或只是通过简单的迁移进程来降温，而且常以取得较低的平均温度或平坦的温度曲线为目标。然而为保证处理器正常工作，重要的是保证温度不超过某个阈值，平均温度的高低相对次要。有实验表明，不同任务对处理器的温度有不同程度的影响，其差别甚至十分巨大，所以通过任务在不同核间切换和单个核上的调度降低处理器的峰值温度是可行。本文以数字温度传感器(DTS)为硬件基础, 以基于热传递原理的模型为理论出发点，以任务调度为手段，以降低处理器的峰值温度为目标。首先探讨任务调度在单核上的性质，提出了热优先排序和冷任务插入方法，然后将得到的结论扩展为多核，提出了任务分配原则和冷任务迁入方法。该方法性能损失较小，而且可与DVS和clock gating方法共同使用。 1.多核调度 多核调度是单核调度的扩展，多核处理器每个核上的调度都保有上节所讲的性质。多核调度从一般可以分为全局调度和局部调度。目前局部调度应用较广泛，本文采用局部调度，将调度步骤主要划分为分配、核上调度和核间迁移。
多Agent系统及其组织结构
计箨机应用研究２０００车 多Ａｇｅｎｔ系统及其组织结构 赵龙交１３候义斌‘ （１西安霆逯走擎工程与耪攀研究琏骛资７ｌｏｏ毒９）＜２鸯癌棱技拳磺究辑西安露００２蛰 摘要组织结构为Ａｇ∞ｔ成员提供一个相置也闻交互的框架，谛每个Ａ鲫诚员挺僻一个多Ａｇ酬群体 求解问题的商层观点和相关捕息。诗论了Ａｇｅｎｔ的概念和姑构。井根据多Ａｇ廿ｌｔ系纨的特点和目标，络出和分析了多删系统的蔓艮成和三种组织蛄构。 关键词Ａ彗材哇盎制体奏觚ｓ虹织结构 ｌＡｇ∞ｔ的概念 Ａｇｅｎｔ是一个运行于动态环境的具有较高自制能力的实体（即自制体可以是系统、机器等：软件Ａ斟ｎｔ是一个计算机软件程序），其根本鞋标是接受另外一个实薛（繇主搭霹壤是嚣ｌ产、幸｝舞壤疆亭、系统戢梳嚣等）的委托弊为之提供帮助和搬务，能够在该秘标的驱动下主动采取包括社交、学弼肄手段在内的各种必要的行为以赙知、适应并对动卷环境的变化进杼适当的反应，它与其服务主体之翘典岿较为松散和相对独立戆关系。 趣咖不是自期和提供帮勘两种属性静簿革结台，而是二者有机的统一体。为燕体提供帮助和服务尾Ａｇｅｎｔ的目标和本质．自制是戴属性和实现其目标所应该采取的簪段。Ａｇ酬的所群岛割｛亍为均是以般嘉教遣势用户提撰黎助为基静瓣，Ａｇ畦技零瓣零震箍是研究如旃搜一个或多个实体嚣可髓地不打搅用户、依靠其自身的能力、采甩各种可能的方法和技术完成用户所委托的艟为复杂或烦瑚的任务．因此，一个Ａｇｅｎｔ应该尽Ｗ能准确地理解用户的真实意图，戗括帮助用户方裁、准确缝播述釉寝达任务意强，浆敬各种鑫蓦标鞋韵瓣、糨摄主韵辩搿为。摇社交、学溜、推理、合作普：蒋知并适应复杂的和不断变化的动；嚣环境；有效地利用环境中的各种埘能利用的数据、知识、信息和计算摄源．为用户提供迅捷、准确和满意齄帮助。 ２矗零贰鹁蒸奉鳍掬帮氧弧Ｓ≤醚Ｈ珏ｌ－Ａ￡描ｌＳｙｓｔｅＩｎ） Ａｇｃｎｔ的基本结构如图ｌ所示．由环境感知模块、执行模块、通讯模块、信息处理摸抉、决策与智能控濑ｌ模块跌及知识麾和任务表组成。邸境感知模块、执学筷块窝逶谖模块受责专幕统球缓帮其它Ａ辞珏ｔ避褥交互，任务袭为该Ａｇｅｎｔ所要完成舶功程和任务。镄息处理模块负赏对感知和接收到的信息进行初步地加工、处理和存储．决策与智能控制模块是赋予＾ｇ蝴ｔ姆能的关键部件。它运用蛔识库巾脾知识对信息嫩蠼 牧稿日期：２０。。年１胃２１日模块处理所得到的井部环境信息和其它Ａｇｅｎｔ的通讯信息进行谶一步的分析、推理，为进一步的通讯或从 任务表中选择适当的任务供执行模块执行作出台理的决燕。程燃ｓ中，各Ａｇ瞅怒蠢制斡。各Ａｇ粼乏间只能透过逶谶跬爱对拜麓黯敬囊镬互影噙，各Ａ鬈ｃ珏ｔ鑫身的行为最终是由其自己决策的。甾＼阻罄港 图１＾倒的蒜潜鸿｝构 Ａｇ器谴投术靛两个主要发展方寅是捣筑嬉德复杂、鲡镑率富帮殛耗强文秘募Ａｇａｔ系统和虫多个结构和性熊较为简单的Ａｇ锄ｔ缀成一个ＭＡｓ。遄垃多个 Ａｇｃｎｔ之问的协作，使整个累娩具有丰富的知识和强大的功能。所谓ＭＡｓ是指出雾个蛳ｔ组成的一个较为松散蛇多Ａｇｅｎｔ联邦，这烂Ａｇｅｎｔ成员之间相互协嚣，招蔓瓣务，共嚣完袋一个任务。砻敏聪娥晏静括动是自制和独立的，其自街的目标和行为布蹙其它Ａ嚣ｎｔ成崩的限制，它通过巍争或磋商等手段协调和解决各成员Ａｇｅｎｔ的目标和行为之间的矛盾和冲突。ＭＡｓ卣奇数描和资源是分散的，每个Ａｇｅｎｔ对予所要完纛羲｛王势绷骞不全器瓣信感残髓力，摹存在垒嚣魏控制系统，任务昭执行和计算怒异步柏。Ａ弘ｓ主簧研究整个Ｍ＾ｓ精动中各Ａｇ龃ｔ之间的相互作用如何产生、每个Ａ蹦ｌｔ成员的推理和行为决莆如何考虑蔗婉或环境中其它Ａ龄ｎｔ的存在、Ａｇｅｎｔ成员蛉日标和行为之间霹藐翦｛中突捡涮釉协调跌疑强务靼赍添瓣划分、努配帮管理等。 ３ＭＡｓ社会及其组织结构 ＭＡ８的姐织结构为Ａ萨ｎｔ成员提供一十棚强之间交互的框槊，为每个Ａ鲫ｔ成员提供一个多＾嚣耐群体求簿闯露的离屡鼹点和相蓑攘塞，鞋便合理地势聚任务著蓬这簸Ａｇ％嘧漫戆镑嚣姆琏貉蠢工捧。糍好藏、 万方数据
基于贡献度的项目调度方法研究
第14卷第12期计算机集成制造系统 Vol.14No.122008年12月 Computer Integrated Manufacturing Systems Dec.2008 文章编号:1006-5911(2008)12-2431-05 收稿日期:2007-12-24;修订日期:2008-04-28。Received 24Dec.2007;accep ted 28Apr.2008. 基金项目:国家973计划资助项目(2005CB724100);国家863计划资助项目(2007AA04Z110,2007AA04Z190);国家自然科学基金资助项目 (70271053,70772056)。Foundation items:Project supported by the National Basic Resear ch Program ,China(No.2005CB724100),th e N ational H igh -T ech.R&D Program,China(No.2007AA04Z110,2007AA04Z190),and the National Natural Science Founda -tion,China(No.70271053,70772056). 作者简介:管在林(1966-),男,江苏高邮人,华中科技大学机械科学与工程学院副教授,博士,主要从事约束理论、制造系统建模与仿真等的研 究。E -mail:zlgu an@h https://www.wendangku.net/doc/ce4376105.html, 。 基于贡献度的项目调度方法研究 管在林1,马 力1,何 敏2,邵新宇1 (1.华中科技大学机械科学与工程学院数字制造装备与技术国家重点实验室,湖北 武汉 430074; 2.武汉烽火通信科技股份有限公司,湖北 武汉 430074) 摘 要:为改进传统的项目管理方法,提出了一种由统计理论得出的指标)贡献度来决定在关键链识别过程中的冲突解决策略,以达到识别出项目关键链的目的。为使调度计划在不确定性环境下能够顺利实施,该调度方法充分考虑了项目执行过程中工序的随机性。在此基础上,提出了一种关键链识别方法,最后针对标准问题库PSPL IB 中的典型算例,应用M atlab 进行了仿真验证。 关键词:项目管理;项目调度;关键链;瓶颈;贡献度中图分类号:T P391 文献标识码:A Project scheduling method based on the contribution index G UA N Zai -lin 1 ,MA Li 1 ,H E M in 2 ,SH A O X in -yu 1 (1.Stat e K ey L ab of Digital M anufact ur ing Equipment &T echnolo gy ,School of M echanical Science &Eng ineering ,H uazhong U niversit y of Science &T echno lo gy ,W uhan 430074,China; 2.Fiber Ho me T elecommunication T echnolo gies Co.,L td.,Wuhan 430074,China) Abstract:T o improv e tr aditional pro ject manag ement methods,a conflict r eso lutio n strateg y in identify ing the cr itical chain of the pr oject by using the contributio n index co ming fr om the st atistical t heo ry was pro po sed.T o r ealize smo oth implementatio n o f project scheduling under uncer tain env ir onment,the r andomness o f the pro ject procedur e during the pr oject ex ecution pr ocess w as taken into consideratio n in this method.Based o n the str ategy ,a new crit-i cal chain identificat ion metho d was int roduced.Finally ,based o n one standar d instance f rom the w ell know n PSPL IB benchmar k set,simulatio n ev aluatio n to this method in M atlab env ir onment w as pr esented.Key words:pr oject management;pro ject scheduling ;critical chain;bott leneck;co nt ribution index 0 引言 在当前装备制造业成为我国重点发展方向的背 景下,有必要改善传统的项目管理理论与方法,验证新方法的可行性,并最终将其应用在大型机电装备的设计、加工和装配过程的规划与管理过程中。 高德拉特(Goldratt)博士于1986年提出了约束理论(T heo ry of Co nstraints,TOC),强调以系统 整体的观点进行生产管理。之后,他将TOC 引入到项目管理领域,提出了一种基于瓶颈识别及缓冲管理的新方法)))关键链项目管理(Critical Chain Project M anag em ent,CCPM )方法[1]。传统的关键路径法(Critical Path Metho d,CPM )在确定关键路径时,主要依据预先估计的任务时间与任务间的逻辑关系,并没有充分考虑资源约束对项目计划的影响 [2] 。而CCPM 方法则认为决定整个项目效率的
面向LTE-V调度方法研究
技术 专栏5G与车联网5G and Internet of Vehicles特约主编朱雪田 面向LTE-V调度方法研究 李艳芬，朱雪田 (中国电信股份有限公司智能网络与终端研究院，北京102209) 摘要：智能出行推进车联网从支持车载信息服务向支持V2X服务的下一代车联网发展，为了满足车联网发展需求,3GPP标准针对LTE-V制定了PC5接口和Uu两种通信方式。结合LTE-V业务特点，介绍了Mode3、Mode4、SPS 增强调度算法及各算法优缺点，为车联网车车、车路、车人之间低时延、高可靠性的通信需求奠定基础。 关键词：PC5；Uu；Mode3；Mode4；SPS增强 中图分类号：TN929.5文献标识码：A DOI:10.16157/j.issn.0258-7998.190882 中文引用格式：李艳芬，朱雪田.面向LTE-V调度方法研究[J].电子技术应用，2019,45(9):8-12. 英文引用格式：Li Yanfen,Zhu Xuetian.Research on LTE-V scheduling method[J].Application of Electronic Technique,2019,45 (9):8-12. Research on LTE-V scheduling method Li Yanfen,Zhu Xuetian (Intelligent Network and Terminal Research Institute of China Telecom Co.,Ltd.,Beijing102209,China) Abstract:Intelligent outgoing promotes vehicles networks from supporting on-board information services to the next generation that supports V2X services.In order to meet the development needs of Vehicles networks,the3GPP standard has developed two com-munication modes,PC5interface and Uu,for https://www.wendangku.net/doc/ce4376105.html,bined with the characteristics of LTE-V services,this paper introduces the Mode3,Mode4and SPS enhanced scheduling algorithms,and the advantages and disadvantages of each algorithm,which lays a foundation for the communication requirements of low-latency and high-reliability among V2V,V2I and V2P. Key words:PC5；Uu;Mode3；Mode4；SPS enhanced 0引言 车联网的提出和发展可以有效缓解或解决由于车辆快速增长而带来的各种问题，并有可能彻底改变人们未来的岀行模式，大大提升道路交通网络的运输效率、安全水平、智能化水平及环保水平，对支撑汽车产业升级转型具有重要意义。车联网是以车内网、车际网和车载移动互联网为基础，按照约定的通信协议和数据交互标准,在V2X(Vehicle to Everything)之间进行无线通信和信息交换的大系统网络，是能够实现智能化交通管理、智能动态信息服务和车辆智能化控制的一体化网络。 1LTE-V标准进展及业务需求 国际上车联网标准包括两大通信阵营，一种是DSRC(Dedicated Short Range Communications)方案，作为WiFi的升级版技术。美国在1998年将5850-5925 MHz用于DSRC无线电服务，也是多数企业普遍采用的标准。另外一种是以LTE为基础的车联网专用的LTE-V方案，实现车辆与周边环境节点低时延、高可靠的直接通信，满足行车安全需求。 3GPP标准进展如图1所示，2015年12月，3GPP RAN启动LTE-V的第1个工作项目，主要完成基于LTE PC5接口的V2V(PC5-based V2V)的标准化工作。2016年6月，3GPP RAN启动第2个LTE-V工作，主要完成基于Uu接口的LTE-V,以及其他第1阶段遗留的标准化工作。2017年3月,3GPP RAN启动基于Rel-14 LTE-V的增强(Rel-15)的标准化工作，截止到2018年6月完成了LTE-V R15标准制定，同时6月份正式将eV2X列为R16标准化研究内容。5G eV2X可为自动驾驶汽车提供更多的无线通信功能以支持多种前沿用例，如车辆间高吞吐量传感器数据及地图共享，将车辆摄像头捕捉到的信息流传输至其他车辆以实现“透视”功能，或实现宽带测距以改善定位服务。3GPP主张未来5G eV2X是LTE-V的一个补充，而不是后向兼容。 目前主要产品形态还是基于R14,在R14中针对LTE-V定义了三类业务场景，分别是安全应用场景、交通效率提升应用场景、信息娱乐服务场景，共计27种用例⑴。对网络有如下需求： (1)速度：支持最高相对速度为500km/h,最高绝对速度为250km/h； 8欢迎网上投稿www.ChinaAET.c om《电子技术应用》2019年第45卷第9期
求解作业车间调度问题的全局邻域搜索方法
第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.wendangku.net/doc/ce4376105.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 完备问题存在有限时间内的可行解,
制造业车间作业计划与调度研究
制造业车间作业计划与调度研究 车间作业计划（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）合理性。综合上级计划、在制品进展情况、工序周期、工序时差和剩余工作量等因素，通过合理地排程方法，达到满足交付和有效利用资源的目的。
水库优化调度方法研究分析
水库优化调度方法研究分析? 崔瑞红，董增川 (河海大学水文水资源与水利工程科学国家重点实验室，江苏南京 210098) 摘要：水库优化调度对水资源的合理利用具有很重要的意义，本文从其调度所采用的优化方法方面分析了国内外水库优化调度的研究的进展。对几种代表性的方法在水库优化调度中的应用列表分析比较，最后对今后水库优化调度方法的研究发展作了展望。 关键词：水库优化调度，优化方法 1 概述 水库优化调度是一个多阶段决策过程的最优化问题, 是在常规调度和系统工程的一些优化理论及其技术的基础上发展起来的。其基本内容可描述为:根据水库的入流过程,遵照优化调度准则,运用最优化方法,寻求比较理想的水库调度方案,使发电、防洪、灌溉、供水等各部门在整个分析期内的总效益最大。通过水库优化调度，可以解决各用水部门之间的矛盾，经济合理地利用水资源及水能资源，因而，在现今我国乃至世界水资源贫乏、开采利用不合理的情况下，水库优化调度具有非常重要的意义。开展水库的优化调度研究工作，提高水库的管理水平，几乎在不增加任何额外投资的条件下，便可获得显著的经济效益。 关于水库优化调度的研究最早从20世纪40年代开始，美国人Mases于1946年最早将优化概念引入水库优化调度。国内的相关研究则是从上世纪60年代起步。华中科技大学的张勇传是国内水库优化调度的开拓者。这些年，随着系统工程优化理论和数学规划理论的日臻完善，随着计算机技术在这两大领域的应用，水库优化调度的方法也愈加丰富。从径流描述上分，一般可分为确定型和随机型两种；从所包含的水库数目划分，可分为单库优化调度和水库群优化调度两方面；另外，赵鸣雁等人从库群目标函数和相应的约束条件方面把水库优化调度划分为：显随机优化方法、隐随机优化方法、多目标优化模型、有预报的实时控制、启发式规划模型以及其他模型六种。单从优化调度所采用的优化方法划分，一般可分为线性规划、非线性规划、动态规划、多目标优化和大系统协调法、新算法等。本文从其用的优化方法方面进行总结和评述。 2线性规划非线性规划方法 2.1线性规划 线性规划是水库优化调度中较简单且应用广泛的规划方法。这种方法不需要初始决策，结果收敛于全局最优解，在大规模问题的求解中用的较多。1973年，Windsor最早把线性规划应用于水库群的联合调度[1]。Needham等人于2000年将线性规划的混合整数规划方法应用于Lowa and Des Moins River的防洪调度，指出作随机评价时，该方法耗时很多[2]。国内的王厥谋（1985）建立了一个线性规划模型进行防洪优化调度。许自达（1990）用线性规划方法求解了并联水库群联合调度。线性规划法计算效率低，由于水库优化调度是非线性和随机性，当调度的目标函数和约束条件很复杂时，需先用其他方法将问题线性化再进行求解。 收稿日期：2006-04-14 作者简介：崔瑞红(1982—) 女(汉族) 山西人 硕士研究生 主要从事水资源规划与管理的研究