数学建模调度问题范文

导语：如何才能写好一篇数学建模调度问题，这就需要搜集整理更多的资料和文献，欢迎阅读由公务员之家整理的十篇范文，供你借鉴。

篇1

【关键词】铝箔 加工 排产 优化

铝箔的生产，在工艺方面和材料的使用方面要求都比较高。需要的工艺流程复杂，要经过焙铸、热轧铸轧、冷轧、箔材轧制、分切等加工工艺和热处理过程才能对铝制品进行加工，工序比较长、难度比较大。铝箔的生产技术不断的发展使我国在铝箔方面的消费比例不断的提高但是铝箔的生产水平还依然存在很多问题，对于加工方法还有待研究。本文对超薄铝箔的加工动态集成排产方法进行研究。

1热轧问题的使用方法

1.1数学规划方法

在热轧的问题上，我们早期使用的方法是数学规划的方法。数学规划模型的使用是利用动态的规划方法对离散钢铁企业的优化生产问题进行解决的。PVC板生产中的多开工时间调度问题开发出了一种TABU搜索启发的算法，这种算法的应用很大程度上减弱了开工时间的调度问题。分支界定算法的出现是对无缝钢管的轧制进行多阶段的分批调度问题的解决。而在轧机、加热炉、能力损耗和制造成本方面的调度目标模块所使用的是分支界定求解的方法。在国外，这几种方法得到了广泛的应用但是应用的时效性受到了限制。

1.2非数学规划的方法

非数学的规划方法可以分为两大类，主要是启发式方法和人工智能的方法。启发式方法是通过对计算过程和评价指数的运算在比较短的时间里，有意识的寻找最佳的解决方案。COWLING提出了一种决策系统，这种决策系统是以钢铁热轧过程的多模型为依据，利用TSBU的算法对调度问题进行有效的解决。热轧调度问题的简化是PCVRP的模型，同时提出了基于大规模邻域定义的局部搜索方法。模拟退火算法有时候也被用于求解热轧调度的相关问题。

1.3数学模型的建立

我国的研究者陈雄创造出了轧制批量计划问题的数学模型，这种数学模型分为启发式算法和模拟退火算法。我国在热轧批量计算问题的约束满意问题进行了处理，对轧热问题的PCTSP建模和该模蚁群的蒜放方面做出了研究。针对轧热问题的CVRP建模还提出了混合免疫算法。

上述的这些方法都是轧制生产中的优化排产的基本理论和方法。由于我国超薄铝箔的生产不断的发展，生产要求也随之提高，在排产计划和热处理方面要使生产具有动态性就要根据具体实际进行任务的不断完善和添加，随时对排产计划进行调整，排产的相关实时性要求和方法要快速的计算，增加可靠性和实用性特点。

2代数法建模

2.1符号函数的定义方法

I设置为铝卷号，I=1，2...，P。J为设备的编号，J=1，2，...，M。工艺路线矩形阵R。R是n*m型矩阵，其中元素R表示铝卷I在加工工艺路线中设备J所占的顺序位。铝卷号关系表E%表E中每行代表一个铝卷号的属性、各列分别表示物料编码、炉架号、直径、计划开始时间、加工时间、设备编号、工艺顺序号其中物料编码、设备编号、工艺顺序号、加工时间的数据来源于工艺路线矩阵和加工时间矩阵。图1所示为炉架和铝卷的几何尺寸其中a、b、h分别代表炉架的长、宽、高。条件如下所示：

H=h1+h2+h3

r1>r2>....rk rk+1>rk+2>....>rk2k

上排

h1>r1 h2>r1 u1=r1 u2=r1+r2

下排

H3>rk+1 h2>rk+1

图1.炉架和铝卷的几何参数

2.2第一次排序

第一次排序是对订单池中的铝卷进行排序，排序按照重要的程度和紧急的程度进行安排，优化的准则体现在评价指数当中。对调度问题的NP难度性，要选择计算量不大，计算时间不长的效果优化好的启发式目标函数作为评判的标准。

兼顾能够对设备的使用率提高、合同按照完工率和装炉系数等进行多样性目标的归集，评价的指数可以参照铝卷号和炉架号进行归类。第一次排序是对任务中的全部铝卷进行加工，按照从小到大的顺序进行排序。

2.3第二次排序

第二次排序是第一次排序的升级，把第一次排序截取的归属于统一最佳的铝卷进行内部的排序，使吕佳能够安装更多的铝卷，这样能够节省热处理电费。这种方法也被称为炉次计划，计划的步骤主要体现在：

首先，在按照排好的序列中从前向后截取铝卷直径之和小于或等于2a最好接近2a的铝卷子序列。

其次，从这种子序列中对铝卷进行选择，每隔一个选取一个，按照铝卷的直径大小排列，排列顺序是由小到大的排列顺序。

最后，将该两段铝卷分别摆放在支架的上下两排，对每个铝卷的位置是否满足约束条件进行检查，如果符合则排产成功，进行下一步，如果没有成功就要对两端序列进行保留。截取两端子序列，在四段中选配评价指数最小的又能满足条件的方案。然后输出铝卷的两次排序方式和炉架上的摆放方式。

2.4状态赋值

当设备为退火炉时，设定编号为K，设备轧机时设定编号为J。这种情况下设备的变量的计算方式主要有三种，分别表示为：

首先，设备编号为轧制设备时每一个炉架的第一铝卷开工时间为上一道热处理时间与本轮最后一个任务完成时间的最大值。每一个炉架非第一个铝卷轧制工序设备加工最近的铝卷被上一道工序加工完毕是具有以下公式：

在设备J没有加工铝卷时，铝卷被上一道程序加工时的公式是：

在这里i表示设备k加工的上一道铝卷，热处理工序的状态时间是在当前设备加工的前一个炉架的结束时间和当前铝卷时间的最大值。

3结语

综上所述，本文从铝卷的排产方法、炉架的布置以及生产的调度方面对超薄铝箔的生产排产方法进行了研究。按照订单的需求进行先后的排序，在同一个铝卷在炉架上的合理排放方式进行了分析。超薄铝箔具有工艺流程复杂性的特点，我们要对对象进行合并、分割、集中的特点运用相应的代数方法进行模型的建立以此促进按时完成订单和节能减排的一员。

参考文献：

篇2

【关键词】车辆调度；物流配送；多车型

【中图分类号】U492.2 【文献标识码】A

配送车辆调度问题是运筹学和组合优化领域的热点问题.多车型配送车辆调度问题是配送车辆调度问题的一个分支，一般情况下，配送企业为了适应配送商品种类繁多、性质各异、客户要求各不相同的情况，往往配置多种类型的配送车辆，以提高车辆的满载率，降低配送成本.可见，研究多车型配送车辆调度问题具有重要的理论和现实意义.

本文在现有研究成果的基础上，建立了多车型配送车辆调度问题的基于直观描述的数学模型，考虑的目标函数和约束条件比较接近实际，决策变量、目标函数和约束条件的表示较为自然、直观和易于理解.

1.对多车型配送车辆调度问题的描述

现实中的多车型配送车辆调度问题十分复杂，为了方便建模和求解，需要对现实问题进行一些抽象和简化.现对本文研究的多车型配送车辆调度问题作如下描述：

1）从一个配送中心向多个客户送货，配送中心供应的货物能够满足所有客户的需求；

2）各个客户需求的货物均可以混装，单一客户的货物需求量不超过配送车辆的最大载重量，每个客户的送货要求必须满足，且仅能由一辆车完成，不允许分批配送；

3）配送车辆按载重量分类，每种车型的最大载重量一定且不允许超载，每种车型

的一次配送最大行驶距离一定，不允许超过.配送车辆均由配送中心出发，向一些客户提供配送服务，最后返回配送中心；

4）配送中心与客户之间及客户相互之间的最短距离已知且固定.

在满足上述条件下，我们要求运输成本最小.

2.构建数学模型

现有一个有向图G=（V，E），其中V={0，1，…，N}有N+1个顶点，E={（i，j）|i，j∈V，i≠j}表示弧集，顶点0表示配送中心，剩余的顶点集V′=V＼{0}表示N个配送点，为构建多车型最小费用车辆路径问题数学模型，定义以下参数：

gi： 配送点i的需求量；

φ={1，2，…，L}为车辆类型的集合，类型总数为L；

Kl：l车型的数量；

φl：车型l的车辆数集，φl={1，2，…，Kl}；

dij： 两个节点间的最短距离，i，j∈V；

Ql： 车型l的装载能力，Q0l表示车型l的空重；

cl： l型车每公里每吨的载重费用，单位：元/吨・公里；

clkij： l型车的第k辆从第i点到第j点的费用，与距离和载重有关：

clkij=dijclrlkij（i，j）∈E；l∈φ；k∈φl；

rlkij： l型车的第k辆从第i点到第j点车辆的重量；

xlkij=1 l型车的第k辆从第i点行驶到第j点0 否则

式（1）表示目标函数，即总配送成本最小；

式（2）保证车辆都是从配送中心出发，最后回到配送中心；

式（3）表示进入每个货物需求点的车辆卸载后会离开；

式（4）、（5）确保每个货物需求点只能被一辆车服务一次；

式（6）表示车辆承载的货物量之和不得大于车辆的容量；

式（7）是递推车辆行驶路径的总车质量；

式（8）是车辆回到配送中心时车辆的重量；

式（9）是不超过车辆的装载能力；

式（10）是经过某一配送点时车辆重量不能小于空车重量；

式（11）是l型车的第k辆从第i点到第j点的费用计算公式.

3.算法过程

在多车型低耗车辆路径问题解决过程中，本文采用爬山算法作为求解的主要算法.爬山算法是一种局部择优的方法，它采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策.该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解.属于人工智能算法的一种.爬山算法结构比较简单，在某些情况下，整体效率还是很好的.但它的主要缺点是有时会陷入局部最优解，而不一定能搜索到全局最优解.但由于它求解时可以把复杂问题简单化，且解的结果与最优解比较接近，所以在很多领域中都有着广泛的应用.

爬山算法的基本步骤如下：

第一步：输入多车型低耗车辆路径问题，包括配送中心、顾客点之间的坐标，配送

点需求，车型参数（载重能力、空重、不同车型固定成本）等.任意选定一个初始解x0，记录当前最优解为xbest，且令xbest=x0，令U（xbest）代表xbest的邻域.

第二步：从xbest的邻域U（xbest）中按照某一规则选出一个解xnow，转到第三步；

若当U（xbest）=φ时，或满足其他停止运算的规则时，转到第四步；

第三步：计算xnow的目标函数值minZ1，若xnow的目标函数值minZ1小于xbest的目标函数值minZ，则xbest=xnow，minZ=minZ1，U=U（xbest），转到第二步；否则 U=U-xnow，转到第二步；

第四步：输出计算结果，停止.

在爬山算法中，第一步的初始解可以采用随机方法产生，也可以用一些经验方法或者采用其他算法得到初始解.第二步中在U（xbest）中选取xnow的规则也可以采用随机选取的规则.

4.实验计算和结果分析

实例：设配送中心（0，0）和16 个客户配送点分布及需求情况，具体数据见表1，假设该配送中心有3种车型，见表2.根据以上的爬山算法，我们应用Lingo语言来求解，获得费用最少的行驶路径，见表3，此时费用为3654.40元.

5.结 论

总的来说，对于复杂的VRP，如果仅凭决策者的经验，是很难在较短时间内作出一个合理的运输路径规划的，本文利用优化模型，采用爬山算法，再通过Lingo自动搜索得到费用最少的最优路径和车辆调度数.最终结果是比较令人满意的.

【参考文献】

[1]杨浩雄，胡静，何明珂.配送中多车场多任务多车型车辆调度研究[J].计算机工程与应用，2013，49（10）.

篇3

【关键词】可分负载 任务调度 可分负载理论（DLT）

调度问题是并行分布式系统研究领域中影响系统性能的最主要的因素之一。常用的对并行分布式系统中任务调度问题的建模主要有两种，一种是基于DAG图的相关任务调度，另外一直是基于可分负载理论（DLT）的独立任务调度。

可分负载指的是任务可以划分成任意数目，任意大小的独立子任务，而这些子任务可以并行执行且不会影响整个任务的最终结果。由于应用上的需求，而可分负载理论在模型的精确性和问题的可解性之间取得很好的折中，近年来使其成为并行调度领域研究的一个新的热点。对于如数据挖掘、图像处理、大规模实验仿真、计算生物学等经典的主从计算范例，可分负载调度可以取得很好的效果。

可分负载的任务调度采用线性模型对网络和应用进行建模，并且充分利用了负载可任意划分的特性，可以使用数学的方法进行分析论证，使得很多重要类型的可分负载问题在特定情况下可以获得近似最优解或最优解，这是可分负载的任务调度获得成功的主要原因之一。

可分负载调度算法按对负载的分配方法可以分为：单轮可分负载调度算法和多轮可分负载调度算法两种类型。

1 可分负载单轮调度

可分负载单轮调度算法就是指主处理机节点将负载划分成块数与从处理机节点数相等的子负载块，然后一次性完成对子负载块的分配处理。

可分负载单轮调度算法设计的主要难点是：

（1）确定主处理机节点给各个从处理机分发任务时的顺序；

（2）确定给每一个从处理机节点分配多少负载量。但是由于后分配的从处理机都要较长的等待时间，所以单轮负载调度算法的效果不是很好。

可分负载单轮调度的研究成果有：

1.1 基本模型

这是研究在最理想情况下的调度问题，即不考虑通信链路的时间延迟，也不考虑机群系统的内存不足的情况。在该情形下负载的通信时间为ai/zi，负载的计算时间为ai/wi（αi表示负载块的大小，zi表示通信速度，wi表示处理机计算速度）。有关资料也证明了在同构系统下，为了使调度的时间最短，所有的处理机都必须参与任务的计算，且任务调度时间不依赖于负载分发的顺序。在异构系统下，则应该按照链路速度递减的顺序进行负载的分发，并且所有处理机必须同时完成负载的计算，这样的话负载就可以在多项式时间内完成计算。

1.2 考虑时间延迟的模型

由于现实的网络中存在通信的启动时间，且每个进程在开始处理数据之前也可能需要先进行一些系统的初始化的工作，为此，在此模型下将负载的通信时间和计算时间分别定义为ci+αi/zi和oi+αi/wi （ci和oi分别表示通信和计算时间的延迟），所以在该情形下，选择所有的处理机产生的效果可能比选择一部分处理机的效果来得低。资料显示单轮可分负载的任务调度异构环境下遵循的原则有：

（1）如负载足够大，则所有的处理机都参与计算。

（2）所有参与计算的处理机都必须同时完成计算任务。

（3）当所有的链路是相同的时候则各处理机须按照c/w的升序进行负载的接收，如果链路速度不同、时间延迟不同则目前还找不到最优的分发顺序。经过分析得出，单轮调度下的新的结论：当链路速度不同，通信延迟时间不同，各处理机计算速度不同时，当则应该按链路速度从大到小的顺序进行负载的分发可得到在给定的比较大的时间内的最优调度。

1.3 考虑系统内存容量有限的模型

以上关于单轮可分负载的任务调度的研究都是在假设系统的内存容量足够大的情形下进行的，而在实际情况中每个处理机系统的内存都是有限的，所以当分发到的负载量大于其内存容量时，则算法是不能有效运行的，且处理机进行任务计算的速度也会受到很大影响，因此内存受限问题是调度算法中不可忽略的问题。有关文献也讨论了内存受限的单层树型网络的异构机群系统下单轮可分负载的任务调度，提出了IBS算法，该算法在每进行一次迭代，都将以一个处理机节点的内存大小为标准分发负载，然后该处理机节点不再参与后面负载的调度。但是该算法没有考虑时间的延迟，为此，后来后者对其进行了改进，提出了既考虑内存不足也考虑时间延迟问题的算法。分析分层存储系统、单层受限存储系统中内存对可分负载的调度性能的影响，给出了在分发顺序已知、考虑内存、考虑时间延迟情况下的周期性可分负载多轮调度的模型，通过设定一个布尔变量表示处理机j是否是分发序列中的第i个处理机的方法，来研究涉及处理机顺序选择问题，并给出了数学模型。

1.4 考虑结果信息返回的模型

在实际应用中存在一些应用在处理完任务后需要将处理结果返回给中心处理节点，如果返回的信息量比较大的话，则返回结果信息的通信时间是不能忽略的。带返回结果信息的可分负载调度中常见的两种通信策略是FIFO策略和LIFO策略。FIFO策略是指从处理机在处理完负载后返回结果信息给主处理机节点的处理机顺序与其在接收主处理机给它分发负载时的处理机顺序是一样的，如果顺序正好相反则是LIFO策略。

专业资料首次研究了这种类型的问题，它解决了两类特殊应用的最优调度问题：一类是通信时间与消息大小无关的常量，这种情况下按LIFO方式是最优的方法；另一类是在总线网上且数据的传输过程中忽略启动开销的情况，在这种情况下按FIFO方式是最优的。而在双工通信模式下，即主处理机节点分发任务的同时可以接收从处理机节点返回的信息的星型拓扑结构下的可分负载调度问题，分别讨论了FIFO和LIFO这两种策略对调度性能的影响，并证明了最佳的结果信息的返回方案既不是FIFO策略也不是LIFO策略。星型网络环境下，采用单工通信模式的考虑结果信息返回的可分负载调度问题，得到了在分发顺序已知、所有参加计算的处理机没有空闲时间情况下的最优调度。

2 可分负载多轮调度

可分负载多轮调度算法是指主处理机节点将应用划分成块数大于从处理机数目的子任务，采用并行多次分配的方法多次将子任务分给各个从处理机节点。其算法设计存在的难题是：

（1）如何确定负载划分的块数；

（2）每块负载的大小如何确定；

（3）从处理机接收负载的顺序如何。

可分负载多轮调度的研究成果有：

2.1 基本模型

有关文献研究了在给定趟数时同构平台下多轮可分负载调度，提出了MI算法，该算法用数学方法得到函数来解决负载块大小的问题，且该文献中给出为了得到好的调度，在分配负载的时候该遵循：

（1）各处理机在接收下一负载块之前要完成当前负载块的计算；

（2）各从处理机完成当前轮负载计算的时候主处理机也完成了下一轮负载的分发。

2.2 考虑时间延迟的模型

关于考虑时间延迟的XMI算法，但是该算法仍然没有提出求解最优轮数的方法。为了使多轮调度更有效，学者们又提出了机群系统下考虑时间延迟的均匀多轮调度算法UMR，该算法通过在同构系统下采用每轮分配给各处理机节点负载量相同、异构系统下使每轮各处理机处理时间相同的策略，给出了求解最优调度轮数的方法，使整体的调度性能得到大幅度提高。在UMR算法的基础上做了扩展，提出了一种可以得到更好调度效果的多轮调度算法RUMR，该算法考虑性能预测中可能存在的错误，通过先从小到大递增负载块，然后再递减负载块的方法进行负载的分配，使得算法更加实用。星型拓扑结构下可分负载的多轮调度问题以及在周期性调度中对相应参数进行优化的问题，并进一步证明了当负载量比较大时，若要得到近似最优的调度算法，应该要保证在通信过程中链路不出现空闲。

以上所提出的多轮调度算法，都假设各处理机都是周期性的参与计算，且计算和通信之间没有空闲时间，所以后来的文献资料只研究了一般的情形，即不要求参与计算的处理机周期性的接收负载，在子负载块数已知的情况下的多轮可分负载任务调度，并分别用B&B方法和启发式的算法得到各负载块的大小及分发的目的处理机号。通过总结分析已有的研究成果，通过设定布尔值的方法，设计了可分负载单轮调度中带处理机的选择问题的算法，并给出了星型网络下参加计算的处理机给定情况下的可分负载多轮调度，不过该算法的目标不是为了最小化负载的处理时间，而是以在给定一个时间内负载块的处理数量的最大化为目标的算法，并给出了详细的证明。

2.3 考虑系统内存容量有限的模型

考虑内存的可分负载多轮调度算法，该算法是在子负载块的块数已知的情况下考虑的。而文献考虑了各处理机的内存问题，提出了UMRLM算法，采用当某轮负载总量超过从处理机的内存容量的时候，使该轮及后面每轮轮负载总量和前一次的负载总量相等的策略避免了由于内存容量不足时UMR不能继续执行的问题，提高了算法的实用性。

2.4 考虑结果信息返回的模型

有关文献考虑了同构系统下带返回信息的多轮调度算法，该文献分别研究了不考虑时间延迟和考虑时间延迟两种情况，但该算法针对的是调度轮数给定的情形。在采用FIFO策略提出了异构机群系统上带返回结果信息的可分负载多轮调度算法。

除了上面的基本模型及其扩展的模型外，近年还有其他一些研究成果，比如：提出了具有两个主处理节点（即由两个处理机来进行任务的分配）的情形，且主处理机能同时和两个从处理机进行通信，得到一个渐进最优的调度。同时还提出了在系统参数未知情况下的可分负载的调度算法，在文献中把负载分发分两个阶段：第一阶段将很小部分的负载分发到各处理机节点，且从处理机节点处理完后向主处理机节点返回信息，然后根据返回的信息估计各个参数，从而根据估计的参数来确定余下的负载的分发，但是该文献研究的是单轮调度。据文献研究了单层树模型下，针对未知网络参数的异构网络系统，提出了一个基于探测技术的多阶段的针对多可分负载任务的调度策略，文中考虑了不知道网络性能参数以及网络性能随时间动态变化两种情形。机群环境下有多个可分负载任务的调度问题，其中文在星型环境下证明了多个可分负载的调度问题是计算难的，只有在一些假设情况下才存在着多项式时间解，在总线型结构下的多个可分负载的调度问题。

上面所有文献资料中所提到的算法都是在从处理机接收完负载以后才开始计算（blocking通信模式），而在大型的应用以及实时系统中，这种模式是不适用的，所以在后面的文献资料中提出了noblocking的通信模式，即从处理机在接收任务的同时就可以开始计算工作。并且得出近似的关于处理时间的表达式及最优的调度顺序。可分负载调度在实际应用当中取得的效果，证明了可分负载调度的实用性。另外，随着多核机器的出现，异构多核机群系统上的可分负载多轮调度算法，系统参数未知的多核异构机群上考虑结果信息返回模型的可分负载多轮调度算法。

3 结语

综上所述，可分负载单轮的任务调度研究的比较透彻，而可分负载多轮的任务调度的研究成果就比较少，且已有的研究成果大多都是假设内存足够大、结果的返回时间忽略的情形，且系统的所有参数都是事先确定好的静态的调度，同时，大多数的研究都是在单核的机群系统上进行的，而在多核机器占主导地位的今天，今后研究在由多核机器组成的机群系统上的可分负载的任务调度就显得尤为重要。

参考文献

[1]李显宁，钟诚，杨锋.异构集群系统的可分负载多轮调度算法[J].计算机应用研究，2008，25（4）：1028-1032.

[2]钟诚，李显宁.异构机群系统上带返回信息的可分负载多轮调度算法[J].计算机研究与发展，2008，45（Suppl）：99-104.

[3]黎鹤，孙广中，许胤龙.未知网络中可分负载的分布式调度[J].中国科学技术大学学报，2009，39（8）：864-870.

[4]Cheng Zhong，Xia Li，Feng Yang，Jun Liu，Meng-Xiao Yin，Yi-Ran Huang. Scheduling Divisible Loads with Return Messages on Multi-core Heterogeneous Clusters with Unknown System Parameters[J].EN.2012（7）.

作者简介

李霞（1980-），女，研究生学历。硕士学位。现为广西财经学院防城港学院教师。研究方向为网络与并行计算 。

篇4

[关键词] 仿真 物流系统 供应链

随着物流系统变得越来越复杂并且内部关联性越来越强，建模与仿真的方法在物流系统的完善和决策中变得日益重要。仿真是利用计算机来运行仿真模型，模拟时间系统的运行状态及其随时间变化的过程，并通过对仿真运行过程的观察和统计，得到被仿真系统的仿真输出参数和基本特性，以此来估计和推断实际系统的真实参数和真实性能。计算机仿真的类型有离散事件(系统)仿真、连续系统仿真、混合系统仿真，还有蒙特卡罗仿真(Monte Carlo Simulation)等。

物流系统是复杂的离散事件系统，在系统设计与控制过程中存在许多优化问题，用系统仿真为解决复杂物流系统的问题提供了有效的手段，它不仅可提供用于决策的定量信息而且可以提高决策者对物流系统工作原理的理解水平，仿真技术为复杂物流系统设计提供了技术性和经济性的最佳结合点和直观有效的分析方法。

因此,物流系统仿真成为近年来国内外学术界研究的一个热点问题。本文对物流系统中的供应链仿真、生产物流系统仿真和物流配送系统仿真进行综述。

一、供应链仿真

供应链管理是一种为适应市场全球化和客户需求多样化而产生的一种管理技术，它能够有效地协调和控制供应链上物料流、信息流、价值流，保持灵活和稳定的供需关系，使整个供应链上企业效益最大化。由于供应链这类复杂系统中存在着很多不确定性和随机性因素，而数学方法由于求解条件的限制，建立的数学模型有时存在着求解困难甚至不可解的结果。在此情况下，以数学模型为基础、以求数值解或特解为特征的仿真建模方法显示出了极强的技术优势。近年来，伴随着许多成熟的仿真软件的引入和使用，各种仿真建模方法解决供应链问题的适用性也得到了大幅度提高。

近年来，很多学者进行了物流与供应链管理的仿真与建模方面的研究。高翔，林杰，张炜等仿真的供应链强调上游及下游企业问的信息共享与相互协作，并根据供应链中不同的信息做出相应的决策。它将整个供应链分为三层结构，即供应商、制造商和销售商，此外还有运输商负责不同层面之间的联系，并通过建模仿真对系统进行优化，提高系统的整体适应能力。

朱卫峰，费奇针对复杂物流系统仿真及其现状进行了研究，给出了复杂物流系统的网络图结构，提出了复杂物流系统仿真CLSim的总体结构，同时指出了复杂物流系统仿真研究的三个问题：复杂物流系统中的不确定性建模、复杂物流系统仿真模型设计与实现及复杂物流系统控制；并将复杂物流系统仿真设计的思想应用于敏捷后勤仿真系统，提出了基于时间步进的事件调度仿真策略，用实体流程图法设计了敏捷后勤系统的仿真模型。

随着电子商务的逐步普及，面向制造企业的传统供应链的结构发生了变化，程曙等运用优化方法理论从供应链的系统性和整体性视角出发，对此种供应链的结构进行详细的建模和仿真研究，寻找具体的决策优化方法，并探讨了其中的目标函数、约束条件等关键性问题。

彭建刚在分析供应链管理的基础上，提出“一流二网三关系”的供应链建模思想：“一流” 指订单信息流；“二网” 指物流网和资源网；“三关系”指客户关系、动态关系和集成关系。同时对供应链建模的混合整数规划和统一优化方法论作了阐述，为供应链的建模提供了较为实用的方法。

彭晨等应用供应链思想对煤炭供应链进行研究，应用Petri网对供应链物流及供应流运行过程进行建模，然后运用子过程分析煤炭供应链存在的问题，最后结合煤炭供应链过程模型运用VB方法完成供应链决策过程的可视化仿真，找出煤炭供应链运营瓶颈。

在二级供应链研究方面，郭士正研究了服务销售系统的二级供应链模型，是关于设施选址和市场顾客配置的混合整数规划问题。在实例应用中，对奶制品零售分销的供应链问题进行了计算机仿真计算。

二、生产物流系统仿真

生产物流是指从企业的原材料采购，车间生产，半成品与成品的周转直至成品发送的全过程中的物流活动。生产物流系统是一个复杂的综合性系统，如何提高其效率和效益是至关重要的，系统仿真作为一项用于系统分析和研究的十分有效的技术，已经被广泛用来对生产物流系统进行规划设计，运输调度和物料控制等。

A．Sawhney(1999)将Petri网技术用于邮件处理中心，对整个处理中心的工作流程进行了分析与优化，提高了邮件处理的效率。

张颖利等对某微型汽车厂总装车间的生产物流系统进行分析研究，在此基础上对其建模和仿真，在仿真过程中可以看到主要部件在装配线中所处的位置，能够判断装配各种零件所需要的时间，方便车间管理人员根据生产需求对生产线进行及时的调整。

詹跃东基于Petri网建模理论，对烟草行业的卷接包车间的AGVS进行了分析，并对该系统构造了Petri网模型。

何腊梅等则以某炼钢厂全连铸改造后的生产调度问题为应用背景，研究了此炼钢生产物流系统的仿真建模与仿真运行问题。在此系统现有流程生产物流的输入条件下。分别对设备在正常生产以及正常检修两种不同条件下进行了仿真试验，得出系统正常运行所需的临界条件。

嵇振平等使用分层有色Petri网(HCPN)和事件操作表(EOL)的方法来减少复杂制造系统建模的复杂性，为物流仿真软件体系结构的模块化及层次化设计建立了良好的基础，并将HCPN应用于宝钢炼钢连铸生产物流仿真系统的建模中。

三、物流配送系统仿真

在现代物流系统中，配送中心是集物流、信息流和资金流为一体的流通型节点，是现代物流系统中的重要组成部分。对物流配送中心，特别是配送中心各个子系统的研究也越来越多。

在配送中心的多个子系统中，分拣系统是较为复杂的，同时又是其核心部分。邵明习等对物流分拣系统进行建模。主要对系统中的设备的选择进行研究讨论．着重描述了分拣设备的动态运行过程，以及速度的选择对分拣效率的影响。

沙洪洲等则是以配送中心的仓储系统为研究对象，建立了其数学模型并研制了计算机仿真软件。在软件平台上，只要给出库存初始参数和出库随机分布就可以清楚地看到库存量的动态变化过程，并预测达到库满或库空所需的时间。

在输送系统研究方面，孙娟等对物流输送系统进行三维动画仿真，在仿真程序中通过对设备参数设定，可以模拟出在这组参数下整个运输系统的繁忙状况及各设备的工作效率，从而对系统的输送能力做出评估。

在物流活动中，科学合理的货物配送路径选择是物流中心在最佳时间选择最佳路径为客户提供最佳服务的有效保证。王英凯等[17]对货物配送最佳路径进行研究，为其建立了一个基于遗传算法的数学模型。并对该模型进行了较为深入的数学处理，给出了智能化配送的路径量化方法。

张汉江等对配送中心的自动化立体仓库可视化问题进行了探讨，采用基于虚拟现实的仿真辅助设计方法，建立了辅助自动化立体仓库设计的可视化仿真的模型。重点论述了辅助自动化立体仓库设计的可视化仿真的设计过程，并以某公司自动化立体仓库设计方案为例，使用该仿真辅助设计软件对方案进行优化调整。

四、结束语

系统仿真作为解决复杂物流系统问题的有效手段，已经广泛应用于生产物流系统、供应链及物流配送系统等研究领域。但是由于实际供应链的复杂性，目前的供应链仿真只停留在理论研究阶段，未能有效地应用于实际的供应链管理中。对真实的复杂物流系统的仿真和总体优化是未来研究的方向和重点。

参考文献：

[1] Kochel P. Solving Logistics Problems through Simulation and Evolution [C]//in the 7th international symposium on operational research in Slovenia Podetrtek，Slovenia．2003

[2]金淳刘昕露:供应链协调的仿真建模方法研究综述[J]．计算机应用研究，2006，23(4)：1～3

[3]朱卫峰费奇:复杂物流系统仿真及其研究现状[J].系统仿真学报，2002，l5(3)：353～356

[4]朱卫峰费奇:敏捷后勤仿真系统设计与实现[J]．计算机仿真，2003，2O(6):4～7

[5]程曙张浩陆剑峰:制造企业双渠道市场的供应链建模和仿真[J].计算机集成制造系统，2004，10(5)：519～522

[6]彭建刚:供应链建模分析[J]．现代管理科学，2004，10：75～76

[7]彭晨岳 东:基于Petri网的流程供应链过程建模分析[J]． 计算机工程与应用，2003，38(3)：199～201

[8]郭士正卢震:二级供应链建模及仿真研究[J].集美大学学报:自然科学版，2004，90)：346～349

[9]Sawhney A，Abudayyeh O．Modeling and Analysis of a Mail Processing Plant Using Petri Nets [J]．Advances in Engineering Software(S0965―9978)，1999，3O(8)：543～549

[10]张颖利邵明习:企业生产物流系统的建模与仿真[J]．物流技术.2005(12)：62～65

[11]詹跃东骆瑛:基于Petri网的物流自动化系统建模与仿真研究[J].系统仿真学报，2001，13(4)：501～504

[12]何腊梅郑忠高小强等:攀铜炼钢生产物流仿真分析[J].重庆大学学报，2004，27(5)：57～61

[13]嵇振平陈文明于戈:分层有色Petri Net(HCPN)及其在宝钢炼钢连铸生产物流系统仿真建模中的应用[J].冶金自动化，2002，27(2)：6～9

[14]邵明习王春峰张沂泉:基于AutoMod的物流分拣系统的建模与仿真[J].物流科技，2006，29(2)：50～53

[15]沙洪洲郭果敢:马尔可夫链用于仓储建模与仿真[J]．计算机仿真，2005，22(4):61～63

[16]孙娟尹军琪宁建国:动画技术在物流仿真系统中的应用[J].起重运输机械，2003(9)：48～50

篇5

针对连续泊位与桥吊集成调度大规模求解困难的问题，提出一种基于滚动策略的优化方法。首先，建立了最小化船舶偏离偏好泊位的成本以及延迟靠泊、延迟离港的惩罚成本的基本的多目标优化模型；然后，采用滚动调度方法根据动态抵泊的船舶抵达顺序将调度过程分成连续的调度窗口，并设计窗口的平移策略、当前窗口对下一窗口的参数更新方式；对每个窗口内船舶进行调度优化，根据每个窗口内的优化结果，更新下一个窗口中数学模型的输入参数；通过选取以船舶数量表示的滚动计划窗口和冻结船舶的数量，持续滚动获得每个窗口的最优解，叠加后获得对所有船舶的靠泊计划。通过算例分析表明，滚动调度能够解决较大规模的调度问题，其效率受滚动窗口大小、冻结船舶数量及滚动次数影响。

关键词：连续泊位分派问题；桥吊分配问题；滚动策略；混合整数规划；集成调度

0 引言

泊位和桥吊都是集装箱码头的稀缺资源，泊位分派问题（Berth Allocation Problem， BAP）和桥吊分配问题（Quay Crane Assignment Problem， QCAP）是提高集装箱港口作业效率的关键。用于符合实际情况的动态连续靠泊计划问题（Dynamic Continuous Berth Allocation Problem， DCBAP）是BAP和QCAP的集成优化，然而集成优化在计算上的困难使得相关研究成果难以得到推广。而滚动策略是码头实际运作计划过程中广泛采用的方法，本文的主要工作是设计DCBAP的滚动优化策略并进行实现。

BAP和QCAP是集装箱港口运作优化领域的热点问题。根据岸线是否连续，可分为离散泊位分派问题（Discrete BAP）[1]与连续泊位分派问题（Continuous BAP）[2]。在离散BAP中，岸线被分为多个泊位，船停靠时一般不能跨越多个泊位，只能处于某个泊位所限定的位置空间；连续BAP则把岸线看作一个整体，船舶通常可以在任意可以容纳它的空闲位置作业。根据船舶抵港时间，可分为静态泊位分派问题（Static BAP）与动态泊位分派（Dynamic BAP）问题。静态BAP指在进行泊位分配时，所有需要安排作业的船舶都已经抵达港口[3]；而动态BAP是指泊位分配开始仍有船舶未到港，未到港的船舶会在分配时间段中的某时刻到达[4]。根据船舶抵达的动态性，依抵达顺序形成序列，为滚动调度提供基础。

BAP和QCAP相互耦合，桥吊对船舶的分配数量直接影响船舶作业时间。将BAP与QCAP独立地分别研究，往往存在一个问题：当港口繁忙时，船舶按照最优靠泊方式靠泊以后，有限的桥吊不能满足其正常作业需求，按时离港；而港口相对空闲时，又可能造成桥吊资源的浪费[3，5]。因此在研究BAP时，需要考虑桥吊数量的限制。Imai等[5]建立了同时优化泊位分配与岸桥调度的模型，考虑了岸桥移动路径优化问题并采用离散泊位分配方法。Legato等[6]以船舶操作时间和岸桥使用数量最少为目标，并考虑船偏好泊位和时间。虽然已有大量文献对BAP建模和设计算法，但是通常都对桥吊分派数量决定船舶作业时间这一条件进行简化，或者简化总桥吊数量有限这一现实条件。例如，Zhen等[7]针对泊位分配问题的不确定性进行了场景分析，并采用启发式算法，解决了40条船舶的较大规模的问题，但忽略了桥吊数量对船舶作业时间的影响。Sammarra等[8]采用禁忌搜索算法（Tabu Search，TS）解决了桥吊分派调度问题，同样未考虑桥吊分派数量对船舶作业时间的影响。目前在靠泊计划中，同时考虑桥吊数量对船舶作业时间影响和桥吊总数量限制的大规模问题（例如80条船舶以上），在文献中尚未见研究。

连续泊位与桥吊的集成调度问题在求解上存在困难，以往研究主要采用的是TS和模拟退火算法等启发式算法或智能算法对简化模型进行求解[8-10]，而基于数学规划的精确算法或启发式算法往往只能获得中小规模问题的最优解或近似解[7， 10-11]。滚动调度法最初主要运用于生产制造领域，它通过反复求解小规模优化问题来取代求解大规模的调度问题[8-10]。Raa等[12]利用滚动策略解决离散泊位下的泊位桥吊集成调度问题，并采用混合启发式算法对窗口船舶进行调度优化。何军良等[13]从能耗角度考虑连续泊位下的泊位调度模型，并提出了滚动式优化决策策略，但并未考虑泊位与桥吊的集成调度问题。

DCBAP同时考虑了船舶的动态靠泊、连续泊位分配、岸桥调度问题，较符合集装箱港口动态优化的实际情形，已有文献对其进行研究。Park等[14]采用两阶段方法，在第一个阶段确定靠泊的位置和分配的桥吊数量，而在第二个阶段确定桥吊对船舶的分派，但是在所研究的算例中，只能获得9个桥吊、40条船舶和1200m岸线的中小规模算例的近似解。韩晓龙等[15]将泊位问题抽象为二维装箱问题，建立了同时考虑泊位和桥吊资源的整数规划模型，并采用启发式回溯算法求解，但求解规模也仅仅为5个桥吊、5条船舶的小规模算例。

相对于已有文献，本文的工作主要是以下两点。首先，本文研究DCBAP，同时考虑桥吊数量对船舶作业时间影响和桥吊总数量限制，建立混合整数线性规划模型，目标函数考虑最小化船舶偏离最优泊位的偏好成本，以及因延迟靠泊和延迟离港引起的惩罚成本三个目标。然后，根据模型的特征，通过船舶动态靠泊顺序分割滚动调度窗口，设计了窗口调度模型与窗口之间参数的更新方法，设计了DCBAP的滚动调度算法。通过大规模算例的验证，得到本文建立的模型和滚动调度算法能够求解大规模BAP，求解性能与船舶数量呈近似线性关系，能够推广用于大型集装箱港口的靠泊计划决策支持系统。

1 基本模型

Kim等[14]在解决DCBAP时，将连续岸线和时间离散化，建立了以时间为横坐标、泊区为纵坐标的二维坐标图表示泊位分配情况。每个矩形表示一个船舶的靠泊计划。每一个矩形的高度取决于作业时间，与分配给它的桥吊数量的函数关系成反比关系。参照Park等[3]建立的模型，本文构建的DCBAP模型考虑以下条件：每一条船舶都有预先设置的偏好泊位；船舶作业时间与作业的桥吊数量成反比，即作业时间不受其他环境因素影响；每艘船舶都有一个最小桥吊数和最大桥吊数的限制，最小桥吊数目一般由船公司决定，只有桥吊达到最小数目，作业才能开始，而最大桥吊数受船长限制；船舶在停泊过程中，作业一旦开始，则必须作业直至必须完全作业完毕，才能停止作业，不得中途停止作业。

下面定义相关集合、参数与决策变量。集合sl={1，2，…，sls}表示船舶集合，k∈sl表示其中一条船舶；sm={1，2，…，sms}表示泊位离散化的分段集合，i，i-，i+∈sm表示其中的分段；而 sn={1，2，…，sns}为计划时间离散化的时段集合，j， j-， j+∈sn表示其中的时段。参数ek表示船k的预期到达时间；ak表示船k的总的桥吊作业时间，以单位桥时计算；bk表示船k的长度；sk表示船k的偏好泊位；c1k、c2k、c3k分别为船k偏离偏好泊位、推迟靠泊、延迟离港的单位惩罚成本；lk、uk分别表示可以分配给船k的最小桥吊数和最大桥吊数；c表示可用桥吊数的总数量；Ai， j表示时空点（i， j）是否被占用；Dj表示j时刻已被占用的桥吊数；M为充分大的正整数。在以上集合的基础上，定义以下决策变量。xi， j，k表示（i， j）是否位于船舶k的靠泊计划矩形区域内，若是则为1，否则为0；zi， j，k表示如果（i， j）点为船舶k的靠泊计划矩形的左下角；vkj表示船k在j时刻是否作业，若是则为1，否则为0；uki表示船k是否在i位置靠泊，若是则值为1，否则为0；Ykj表示j时刻分配给船k的桥吊数量；Ck表示集装箱作业的完成时间，即当Ykj>0时，取j的最大值+1；BLk、BRk分别表示船k停泊位置相对于偏好泊位左偏和右偏的长度；TEk、TLk分别表示船舶k迟于预期离港时间离港和迟于到港时间靠泊的时间差；DLk表示船舶k晚于预期离港时间的时间差。为建模和分析方便，引入以下变量，它们都可以直接通过以上变量和参数表示：

2.1 符号定义

（1）集合

1）为船舶集合，表示其中一条船舶。

2）为泊位离散化的分段集合，表示其中的分段。

3）为计划时间离散化的时段集合，表示其中的时段。

（2）参数

1）：船的预期到达时间。

2）：船的总的桥吊作业时间，以单位桥时计算。

3）：船的长度。

4）：船预期离港时间。

5）：船的偏好泊位。

6）：船偏离偏好泊位的单位惩罚成本。

7）：船推迟靠泊的单位惩罚成本。

8）：船延迟离港的单位惩罚成本。

9）：可以分配给船的最少桥吊数量。

10）：能分配给船的最大桥吊数量，受船长限制。

11）：可用桥吊数的总数量。

12）：表示时空点是否被占用。

13）：表示时刻已被占用的桥吊数，可用桥吊数为。

14）：充分大的正整数。

（3）决策变量

1）：表示是否位于船舶的靠泊计划矩形区域内，若是则为1，否则为0。

2）：表示如果点为船舶的靠泊计划矩形的左下角。

3）：表示船在时刻是否作业，若是则为1；否则，为0。

4）：表示船是否在位置靠泊，若是则值为1；否则，为0。

5）：表示时刻分配给船的桥吊数量。

6）：表示集装箱作业的完成时间，即当时，取的最大值+1。

7）：表示船停泊位置向左偏离偏好泊位的长度。

8）：表示船停泊位置向右偏离偏好泊位的长度。

9）：船舶迟于预期离港时间离港的时间差。

10）：船舶迟于到港时间进行靠泊的时间差。

11）：表示船舶晚于预期离港时间的的时间差。

为建模和分析方便，引入以下变量，它们都可以直接通过以上变量和参数表示 。

1）：表示船的靠泊位置。

2）：表示船的靠泊时间。

3）：表示占用时空点的船。

1.1 模型构建

DCBAP的优化目标包含两方面：一是泊位的优化，即停靠泊位应该尽可能地靠近偏好泊位，以减少集装箱从桥吊到后方堆场的移动时间，提高桥吊作业效率，降低作业成本；二是服务时间的优化，即船舶入港后应尽快靠泊作业，靠泊后尽可能在船公司规定的时间内作业完毕并按时离港。针对这两个目标建立了最小化总惩罚成本的多目标模型，旨在减少靠泊惩罚成本、靠泊等待时间和离港延迟时间。目标函数通过式（1）～（4）定义；而约束函数通过式（5）～（29）定义。

其中：目标函数式（1）为最小化惩罚成本函数，包括船舶停靠泊位水平偏移偏好泊位的总成本、船舶推迟靠泊的惩罚成本、延迟离港的惩罚成本，分别通过 （2）～（4）定义；式（5）和（6）约束了船的停泊位置偏离偏好泊位的水平距离；式（7）～（8）界定了船舶推迟靠停泊的时间差和计算延迟离泊的时间差；式（9）表示船舶必须在到港后才能靠泊；式（10）表示计算船舶离开时刻必须大于等于集装箱作业完成时间；式（11）表示每一个时空点只能被一条船占用；式（12）表示可供分配的桥吊数受总桥吊数限制；式（13）约束了船的作业时间必须要大于等于总桥时；式（14）～（15）反映了作业的持续性，要求作业期间至少有一个桥吊为之服务，即不能中途停止作业；式（16）～（17）限制了可以给每条船分配的桥吊数受最大值和最小值限制；式（18）～（19）建立了Vk， j与Xk，i， j之间的关系；式（20）～（21）建立了Uk，i与Xk，i， j之间的关系；式（22）～（24）保证了船舶靠泊后占用时间和泊位上的连续性；式（25）保证了一条船只有一个参考点；式（26）～（29）保证了船舶靠泊计划矩形内的网格取值为1，矩形外的网格取值为0。

2 滚动调度方法

滚动调度方法是对大规模问题的分解策略，将原问题分解为规模较小的子问题来进行求解，是解决大规模复杂问题的有效手段。刘越洋等[11]针对单机调度问题提出了一种滚动调度策略，有效解决了动态到达的工件在机器上有序加工的调度问题。靠泊计划是一类多处理机任务调度[10]，能够借鉴这一单机调度问题的滚动调度策略。在集装箱码头作业过程中，船舶按照预定靠泊时间陆续到港，船舶按照抵达码头的先后顺序，依次保存在待调度船舶集中等候调度。在滚动调度的操作过程中，将所有船舶分为己靠泊船舶集、待靠泊船舶集、未调度船舶集。其中，已靠泊船舶集指已完成装卸作业或正在进行装卸作业的船舶；待靠泊船舶集指在调度中的船舶，尚未开始作业；未调度船舶集指已经到港但调度计划还未下达的船舶。每次滚动调度优化时，按照一定规则将完成装卸作业的船舶从窗口中移除，并将未调度船舶集补充进船舶窗口中，运用优化算法对当前窗口船舶进行优化，得到该静态调度区间的调度方案[10]。

为了在滚动调度过程中，更新已靠泊船舶的调度信息使之成为待靠泊船舶调度的参数，在式（1）～（29）确定的DCBAP模型的基础上，建立如式（30）～（32）所示的新模型。其中，式（31）拓展式（11）中对于时空点的占位约束，参数A用于表示以靠泊船舶的占位情况，如果已经占位则为1，否则为0。参数A用于设置前期滚动调度中已被占用（“冻结”）的时空点式（32）拓展式（12）的定义，引入D计算每个时段已经被已靠泊船舶占用的桥吊数量，从而更新每个时段的可用桥吊数量配置。参数D用于设置前期滚动调度结果中每个时刻已被占用的桥吊数目。

约束函数式（2）～（10）和约束函数式（13）～（29）。

滚动调度方法将动态调度过程分解为一系列的静态调度窗口，对于各个窗口进行优化获得最优解，然后平移窗口并更新新窗口中优化问题的参数。平移间距和滚动窗口宽度是滚动调度的两个基本因素。平移间距就是当前窗口与下一窗口之间的间隔，一般来说，平移间距越短，滚动优化结果越接近于全局优化，但是滚动优化的迭代次数越大、计算时间越长。滚动优化窗口是第t次滚动时未调度部分内前k个船舶的集合，定义为k（t），k是此滚动调度策略的滚动优化窗口的宽度参数，决定滚动窗口大小。当k（t）是常数时，只有最后一个滚动窗口的船舶个数可能会小于k，其余滚动窗口的船舶个数均等于k。滚动窗口越小，每次调度的船数目越少，调度模型的计算性能越高，但是滚动迭代次数越大，同时全局优化程度也会越低。

在t步的滚动结果中，根据调度结果中船舶的开始作业时间排序，取前λ个船舶冻结。λ为滚动调度策略的冻结窗口的长度，即窗口的平移间距。这λ个船舶的调度并入前（t-1）步的已调度部分S（t）构成下一滚动步骤（t+1）的已调度部分V（t），k（t）内未被冻结的剩余船舶包含在V（t）的补集中。然后从该补集中根据靠泊时间排序选择前k个船舶组成新的滚动窗口k（t+1），如果剩余船舶数量少于k，则取全部剩余船舶。当V（t）包含所有船舶，即所有船舶都已经被调度，则滚动结束，最后一个滚动窗口内的优化调度结果全部执行。

综合以上滚动调度策略的研究，建立连续泊位与桥吊的滚动调度算法流程如下。

步骤1 将所有需要调度的船舶按照到港时间先后排序。并初始化总船舶集合sl，令t=1。

步骤2 初始化已调度船舶集V（t）=，未调度船舶集V（t）=sl；根据集合V（t）中按预期靠泊时间排序的船舶序列，选择前k条船舶，构成滚动船舶集k（t），并更新V（t）=V（t）＼k（t）；根据V（t）中已靠泊船舶对时空点的占位情况更新参数A；根据V（t）中已靠泊船舶在每个时段已经占用的桥吊数量更新参数D。

步骤3 根据式（30）～（32）确定的模型，设置slk（t），求解模型，确定k（t）中船舶的靠泊计划；根据开始时间排序，得到前λ条船舶作为新的冻结船舶，合并已靠泊船舶集合V（t）得到V（t+1）；而剩余的（k-λ）条船舶则与未调度船舶V（t）合并得到V（t+1）。

步骤4 如果V=sls，即所有船舶都已经调度，则停止执行并返回；否则，更新t=t+1，转到步骤2。

3 算例仿真

考虑一个周期48h，泊位码头长1200m的泊位桥吊集成调度计划，以50m为单位对岸线空间离散化，以1h时间单位对计划时间离散化。为48h内到港的20条船舶安排靠泊计划，在初始状态没有任何已靠泊船只。每条船的惩罚成本系数均设置为c1*=100、c2*=200和c3*=300，总桥吊数c=9，取滚动窗口大小为k=5，平移间距为λ=2，其他参数的配置见表1。船舶到达时间ek取自区间[1，36]的均匀分布，船舶偏好位置sk取自区间[1，20]的均匀分布，船舶离开时间dk取自区间[8，14]+ek的均匀分布，船舶作业时间ak取自区间[10，30]的均匀分布。

根据表1中数据（表中下划线表示当前实验下的最优解），采用Cplex作为混合整数规划模型求解引擎，采用C#编写滚动调度算法进行求解，得到48h内20条船的靠泊计划如图1所示。图1中给出每条船舶的靠泊时间、离泊时间、靠泊位置，以及给出了所分配的桥吊数量。每个矩形代表船舶靠泊所占据的时空区间，数字代表该时刻分配给该船的桥吊数量。

滚动策略的主要设计参数是滚动窗口宽度k和平移间距λ。表1是调整k与λ得到的一系列实验的结果。当λ=4时，随着k从5递增到8，总的惩罚成本先递增后递减，在窗口船舶数为7时，目标函数值最小，达到λ=15600。k从5增加到7时，随着滚动窗口的增大，总的惩罚成本减小。因为滚动窗口越大，每次调度的船舶数量越多，局部调度越接近于全局优化的结果。总的惩罚成本减少主要是船舶延迟靠泊成本与延迟离港成本的减少。由于延迟靠泊与延迟离港带来的惩罚远大于偏离偏好泊位的惩罚成本，所以当窗口数增大以后，优化结果更多地偏向于以偏离泊位或者分配更多的桥吊数替代延迟，使总的惩罚成本更小。同时，随着k值增大，桥吊数的利用率更高，桥吊的波动率（即每时刻使用的桥吊个数方差值）更小，桥吊数目更加均衡，桥吊的运营成本相对更低，但总的在港时间略有增加。这说明，港口滚动计划需要港口运营人员与船公司协作共赢，平衡多方利益，以达最优成本。

在滚动调度中，平移间距越小，虽然滚动次数增多，但调度结果也相对更为优化。在表1中，当船舶数量分别为5、7和8时，从四个目标函数和总在港时间看，λ越小，综合结果越优。例如，对k=7的计划，λ从5到4，f、f 1、f 2、f 3和总在港时间的优化比率分别为13.8%、25%、13.7%、0%和5%。其他实验组合也都有明显的优化效果。

滚动窗口从7增加到8时，滚动次数也同时增加，此时，滚动次数增加带来的影响大于滚动窗口增加的影响，总的惩罚成本增加。滚动次数与滚动窗口的大小负相关，与冻结船舶数量正相关。因此，码头在做滚动计划时，需要通过合理匹配滚动窗口和冻结船舶的窗口大小，以使得滚动计划性能最优。

通过控制冻结船舶的数量进行研究，从表1可以看出，随着冻结船舶的增加，惩罚成本增加，滚动性能降低。这是由于系统静态部分的影响。冻结船舶数量增加，每次调度前系统的静态部分增加。即由前一次决策产生的调度，已经调度但尚未完成部分，也会降低系统的性能，影响优化结果。因为静态的部分并未参与后一次的局部优化，导致局部优化并非局部最优。冻结船舶数量设置得过小，又会导致滚动次数过多，计算时间过长。在具体调度中，可通过合理设置冻结船舶的数量，减少静态部分的影响，控制计算时间，提高滚动调度的整体性能。

船舶的到达耦合度对于滚动效率也有较大影响。由图2所示，在不同滚动窗口下，进行第三次和第五次滚动调度时，滚动窗口内船舶惩罚成本都急剧增加，滚动调度效率急剧下降。因为前一时期船舶到达耦合度较高，船舶到达较为密集，集装箱操作量大，使得桥吊操作时间延长，长时间占用大量桥吊和泊位资源，以至于后一滚动期进行滚动调度时，桥吊资源和桥吊资源缺乏，后续船舶不得不延迟靠泊和离港延迟，滚动调度效率受到影响，惩罚成本增加。

影响滚动调度的内因主要在于滚动窗口大小、冻结船舶数量以及滚动次数，因此需要选择合适的滚动窗口大小以及冻结船舶数量来提高总体性能。在选择窗口长度时：一方面要使窗口要足够大，使得滚动窗口内的船舶数量足够多，尽量让所有船舶窗口的局部最优调度方案接近于全局调度方案，从而降低码头的运营成本，提高码头的服务水平；另一方面，窗口大小的选择也需要考虑到优化时间，若船舶过多，局部优化时间过长，可能会延误船舶的靠泊，影响到码头的正常运营，反而增加了时间成本。所以，必须对滚动窗口的大小进行合理控制，提高码头生产系统的作业效率。在此基础上，需要选择合理的冻结船舶数量，使滚动调度性能最优。

表2中的6个实例中，采用滚动调度时，都求得了最优值，而一次调度在船舶规模增长到14条时，就已经内存溢出，无法计算出结果。表明较之于一次调度，滚动调度能够大大降低计算难度，解决大规模问题。

船舶总量从10增长到15时，仅从优化结果上看，滚动调度与一次调度优化结果相近，说明滚动调度的效果较好。由图3可以看出一次调度与滚动调度的运行时间增长趋势，随着船舶规模的增大，一次调度的计算时间急剧增长，船舶总量为10时，一次调度的时间为滚动调度的近两倍，而当规模达到13时，一次调度的时间是滚动调度时间的25倍，一次调度的时间消耗几乎呈指数增长，而当船舶规模增长到14条时，在当前机器上就已经无法计算出结果。相对而言，滚动策略的计算时间增长缓慢上升，与数量几乎呈正比关系。这是因为一次调度需要一次性搜索大量节点，消耗的CPU和内存资源较大。滚动调度计算效率较高，能在有限的时间内完成大规模的优化。

虽然在上文算例中，规模仅为20条船，但是由于滚动策略的计算时间与数量几乎成正比关系，因此采用本文提出的滚动调度方法，能够适应规模无限大的算例，满足实际应用的需要。在根据上文模型和算法进行的实验中，本文已经演算了规模从40～200条船，计划周期从48h到400h的算法，均发现计算性能与船舶数量呈近似线性关系。

4 结语

为解决大规模的集装箱码头泊位与桥吊集成调度问题，本文提出了基于滚动调度策略的优化方法，建立了连续泊位下以船总在港惩罚成本最小的混合整数规划模型。算例分析结果表明该方法可以解决大规模的船舶调度问题，计算性能与船舶数量呈近似线性关系。在滚动调度过程中，滚动窗口宽度和平移间距等滚动策略设计参数对于滚动调度的优化能力和整体性能有着较大影响。随着滚动窗口的增大，调度结果更加优化，运算时间也指数增长。随着平移间距减小，滚动次数增多，调度结果也会更优。在本文的算例中，当k=7，λ=4时，获得的解最优。同时，船舶预期靠泊时间集中情况下，滚动调度的效率会降低。实际调度中，需考量实际情况，对滚动窗口宽度和平移间距进行组合实验和选择，平衡滚动调度策略的优化能力和计算性能，提高码头靠泊计划的效率，降低码头的运营成本和提高码头的服务水平。本文滚动调度策略的设计，利用了DCBAP中船舶预期靠泊时间的动态特征，相对于文献[14]建立的模型而言，虽然计算规模可以大大拓展，但是没有考虑船舶提前抵达并进行作业安排的可能性。另外，采用混合整数规划模型的计算引擎虽然便于研究滚动调度策路的有效性，但是其已然成为制约计算性能的关键，下一步的研究是设计有效的子问题启发式算法融入滚动算法，进一步提高优化能力和计算性能，以满足实际应用的需要。

参考文献：

[1] VIS I F A， DE KOSTER R， Transshipment of containers at a container terminal：An overview[J]. European Journal of Operational Research， 2003，147（1）： 1-16.

[2] KIM K H， MOON K C. Berth scheduling by simulated annealing[J]. Transportation Research Part B： Methodological， 2003， 37（6）： 541-560.

[3] PARK Y M， KIM K H. Berth scheduling for container terminal by using a subgradient optimization technique[J]. Journal of Operation Research， 2002， 53（9）： 1054-1062.

[4] IMAI A， NISHIMURAA E， PAPADIMITRIOU S. The dynamic berth allocation problem for a container port[J]. Transportation Research Part B： Methodological， 2001， 35（4）： 401-417.

[5] IMAI A， CHEN H C， NISHIMUR E， et al. The simultaneous berth and quay crane allocation problem[J]. Transportation Research Part E： Logistics and Transportation Review， 2008， 44（5）： 900-920.

[6] LEGATO P， GULLI D， TRUNFIO R. The quay crane deployment problem at a maritime container terminal[EB/OL].[20130120]. http：///conf/ecms2008/ecms2008%20CD/ecms2008%20pdf/ibsECMS2008_0106.pdf.

[7] ZHEN L， LEE L H， CHEW E P. A decision model for berth allocation under uncertainty[J]. European Journal of Operational Research， 2012， 212（1）： 54-68.

[8] SAMMARRA M， CORDEAU J F， LAPORTE G， et al. A tabu search heuristic for the quay crane scheduling problem[J]. Journal of Scheduling， 2007， 10（4/5）： 327-336.

[9] TAVAKKOLIMOGHADDAM R， MAKUI A， BAZZAZI M， et al. An efficient algorithm for solving a new mathematical model for a quay crane scheduling problem in container ports[J]. Computers and Industrial Engineering， 2009， 56（1）： 241-248.

[10] 杨春霞， 王诺.基于多目标遗传算法的集装箱码头泊位岸桥分配问题研究[J]. 计算机应用研究， 2010，27（5）： 1720-1725.

[11] 刘越洋，席裕.基于两步滚动的单机调度算法研究[J]. 计算机工程， 2004，30（24）： 144-147.

[12] RAA B， DULLAERT B R W， van SCHAEREN R. An enriched model for the integrated berth allocation and quay crane assignment problem[J]. Expert Systems with Applications， 2011， 38（11）： 14136-14147.

[13] 何军良， 宓为建，谢尘，等.基于分布式混合遗传算法的动态泊位分配策略与仿真[J].上海海事大学学报， 2008，29（2）： 52-57.

篇6

关键词:遗传算法;GA;进化;最优化

中图分类号:TP18 文献标识码:A文章编号:1007-9599 (2010) 04-0000-01

Summary on Genetic Algorithm

Gao Ying

(Shandong Industry Vocational College,Zibo256414,China)

Abstract:This article has summarized the genetic algorithm basic principle and the characteristic, as well as in each domain application situation.

Keyword:Genetic algorithm;Evolution;Optimization

一、引言

在人工智能领域中,有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准最优解。在计算此类问题时,若不能利用问题的固有知识来缩小搜索空间则会产生搜索的组合爆炸。因此,研究能在搜索过程中自动获取和积累有关搜索空间的知识并自适应地控制搜索过程从而得到最优解的通用搜索算法一直是令人瞩目的课题[1]。遗传算法简称就是这类特别有效的算法之一。

二、遗传算法基本原理

遗传算法是建立在自然选择和群众遗传学机理基础上的,具有广泛适应性的搜索方法。遗传算法搜索结合了达尔文适者生存和随机信息交换的思想,适者生存消除了解中不适应因素,随机信息交换利用了原有解中已知的知识,从而有力地加快了搜索过程。

遗传算法的基本思想[2]:遗传算法是从代表问题可能潜在解集的一个种群开始的,一个种群由经过基因编码的一定数目的个体组成,初始种群产生之后,按照适者生存和优胜劣汰的原理,逐步演化产生出越来越好的近似解。在每一代,根据问题域中个体的适应度大小挑选个体,并借助自然遗传学的遗传算子进行交叉和变异,产生出代表新的解集的种群。这个过程将导致种群向自然进化一样的后代种群比前代更加适应环境,末代种群中的最优个体经过解码,可以作为问题近似最优解。

三、遗传算法的主要特点及改进

随着问题种类的不同以及问题规模的扩大,要寻求一种能以有限的代价来解决搜索和优化的通用方法,遗传算法正是为我们提供的一个有效的途径,它不同于传统的搜索和优化方法。主要区别在于:

(1)自组织、自适应和自学习性。

(2)遗传算法的本质并行性。

(3)遗传算法不要求导或其他辅助知识,而只需要影响搜索方向的目标函数和相应的适应度函数。

(4)遗传算法强调概率转换规则,而不是确定的转换规则。

(5)遗传算法可以更加直接地应用。

(6)遗传算法对给定问题,可以产生许多的潜在解,最终选择可以由使用者确定。

其中对全局信息有效利用和隐含并行性是遗传算法的两大特点,同时遗传算法对问题本身的限制较少,因而具有很强的通用优化能力。但遗传算法容易过早收敛,这样就会使其他个体中的有效基因不能得到有效复制,最终丢失;而且在进化后期染色体之间的差别极小,整个种群进化停滞不前,搜索效率较低,这样就会导致搜索到的结果不是全局最优解。

自从1975年J.H.Holland系统地提出遗传算法的完整结构和理论以来,众多学者一直致力于推动遗传算法的发展,对编码方式、控制参数的确定、选择方式和交叉机理等进行了深入的探究,其基本途径概括起来有以下几个方面[3]:

(1)改变遗传算法的组成部分或使用技术;

(2)采用混合遗传算法;

(3)采用动态自适应技术,在进化过程中调整算法控制参数和编码粒度;

(4)采用非标准的遗传操作算子;

(5)采用并行遗传算法等。

四、遗传算法的应用领域

遗传算法经过几十年的发展,逐渐被人们接受和运用,遗传算法的应用研究比理论研究更为丰富,下面是遗传算法的一些主要应用领域[4]:

(1)优化问题:优化问题包括函数优化和组合优化两种。函数优化是遗传算法的经典领域,也是对遗传算法进行性能评价的常用算例。对于组合优化,随着问题规模的扩大,搜索空间急剧扩大,这类复杂问题,人们已经意识到把精力放在寻找其满意解上。实践证明,遗传算法对于组合优化中的NP完全问题非常有效。

(2)生产调度问题:生产调度问题在许多情况下所建立起来的数学模型难以精确求解,即使经过一些简化之后可以进行求解,也会因简化太多而使得求解结果与实际相差甚远。遗传算法已成为解决复杂调度问题的有效工具,在单件生产车间调度、流水线生产车间、生产规划、任务分配等方面遗传算法都得到了有效的应用。

(3)自动控制:在自动控制领域中许多与优化相关的问题需要求解,遗传算法的应用日益增加,并显示了良好的效果。例如用遗传算法进行航空控制系统的优化、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习,都显示了遗传算法在这些领域中应用的可能性。

(4)机器人智能控制:机器人是一类复杂的难以精确建模的人工系统,而遗传算法的起源就来自于对人工自适应系统的研究。例如遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等方面得到研究和应用。

(5)图像处理和模式识别:图像处理和模式识别是计算机视觉中的一个重要研究领域。在图像处理过程中,如扫描、特征提取、图像分割等不可避免地产生一些误差,这些误差会影响到图像处理和识别的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在图像处理中的优化计算方面是完全胜任的。目前已在图像恢复、图像边缘特征提取、几何形状识别等方面得到了应用。

五、总结

遗传算法作为一种非确定性的模拟自然演化的学习过程的求解问题方法,在很多领域具有广泛的应用价值,但其在很多方面有待于进一步研究、探讨和完善。可以预期,随着计算机技术的进步和生物学研究的深入,遗传算法在操作技术和方法上将更通用、更有效。

参考文献:

[1]王煦法.遗传算法及其应用.小型微型计算机系统,1995,2

篇7

关键词 网络控制系统；信息调度；静/动态调度；混合调度；调度与控制协同设计

1　引言

网络控制系统（Network Control System，NCS）是指传感器、控制器和执行器通过网络形成的闭环反馈控制系统。目前，大部分关于NCS的研究针对NCS存在的问题和特性建立系统模型、分析系统稳定性、给出控制方法和控制规律，以保证系统具有良好的稳定性和高质量的控制性能。然而NCS的性能不仅依赖于控制策略及控制规律的设计，而且还受到网络通信和网络资源的限制。信息调度尽量避免网络中信息的冲突和拥塞现象的发生，从而大大提高了网络控制系统的服务性能。

2 　NCS中的信息特征与信息调度概念

在NCS中网络传输的信息主要分为两类：实时性信息和非实时性信息[3]。实时性信息对时间要求非常苛刻，如果在规定时间的上限内某一信息未能起作用，则该信息将被丢弃，启用最新的信息。而在NCS信息调度策略中主要调度两类数据信息：周期性信息和非周期性信息。周期性信息是一种实时性信息，一般要求在传输周期时间内必须传送给目标节点，周期性信息也被称为时间触发信息或者同步信息。非周期性信息是指节点间的请求服务等信息，它们的发生时刻是随机的，非周期性信息也被称为事件触发信息、异步信息或者随机性信息。

此外，在NCS信息调度中不能忽视突发性信息，突发性信息指一些事先无法预知的突发性的或者随机的事件（例如报警信号、异常处理等），这类信息必须在一定时间内给予处理，否则系统可能出现异常甚至瘫痪。

在网络控制系统中，信息调度发生在应用层，即传感器、控制器与执行器之间信息传递的过程中。当系统网络中某节点发生数据传输碰撞时，信息调度规定节点的优先发送次序、发送时刻和时间间隔，以避免网络冲突。

在NCS中，如果网络控制系统的所有数据传输都能在任务时限内完成，则称网络控制系统的传输是可调度的。

3　典型的NCS信息调度算法

目前对网络控制系统中信息调度的研究主要分为调度与控制的分开设计和调度与控制的协同设计。

3.1　调度与控制的分开设计

在NCS的研究中，一类研究是针对通信网络，研究提高网络服务质量的信息调度方法；另一类研究是在一定的网络信息调度方法基础上，研究提高NCS性能的控制方法。因此，信息调度方法对改善NCS性能起着很大的作用。

根据信息对实时性的要求，信息调度分为静态调度（又称离线调度）、动态调度（又称在线调度）和混合调度。

3.1.1　静态优先级调度

目前静态调度算法很多，本文着重介绍以下几种典型的算法以及算法的改进。

速率单调静态优先级调度 (Rate Monotonic Scheduling Model) 算法的调度优先级由任务周期确定，在任务周期等于时限的同步实时任务系统中是最佳静态调度算法。但是该算法具有调度判定具有指数时间复杂度、对任务的执行周期限制的过于严格、只能处理具有固定周期的任务等缺点。鉴于上述缺点Lehoczky等[23]提出了扩大调度可行性条件的RM算法。Sha等[22]考虑到任务的阻塞，给出了非抢占服务方式下RM算法的可调度条件。叶明等[5]基于RM算法提出了一种新的实时调度算法(Hard Real-time Communication Scheduler，HRTCS)。文远保等[4]针对任务的周期和调度优先级关系不固定的流媒体提出了改进的RM算法。

截至时间单调调度模型(Deadline Monotonic Scheduling Model )策略的任务优先级由任务时限来决定。该调度算法要防止任务越过其时限而得不到调度，从而影响系统的实时性。当任务周期和时限相同或者所有同步周期性任务时，DM算法都是最佳静态调度算法。

由Hong等提出的基于时间窗的静态带宽调度算法避免了数据在网络传输过程中产生干扰和数据冲突。Hong等还将该调度方法应用于循环服务型NCS和CAN 网下的NCS中。

刘鲁源[6]等鉴于该调度方法只限于调度网络中的周期数据，提出基于同步相和异步相的时间窗调度算法，使非周期数据也可以采用该基于时间窗的静态调度算法。

3.1.2　动态优先级调度

在动态优先级调度算法中，任务的时间约束关系并没有完全确定，新任务的到达时间是未知的。下面介绍几种经典的动态优先级调度算法。

Liu和Layland提出的时限最早的任务优先调度（Earliest deadline first scheduling），任务优先级是任务时限与任务执行时刻的差，该算法对同步周期任务组是最佳的动态调度算法。鉴于EDF是抢占式调度算法，任务间的切换时需要大量开销。Baker[12]给出了非抢占士服务方式下EDF算法的可调度性条件。张惠娟等[11]提出了一种基于EDF算法的优先级驱动实时调度算法，较大程度地克服了EDF算法在多处理器系统中的调度缺点。刘怀等[10]提出了基于EDF算法的容错调度算法。张奇智等[7]采用非中断的EDF调度方法来改善周期性数据帧的端到端延迟。洪艳伟等[1]提出了分别在简单模型上和复杂模型上如何判定实时任务的可行性。

最小松弛优先调度(Least laxity first)和EDF算法可看作同类型的调度算法，任务优先级是完成时限和任务执行时刻的差再减去周期任务的执行时间。LLF算法尽量避免了长周期任务的频繁等待、执行，具有较小的抖动性。

最大误差优先—尝试一次丢弃(most error first-try once discard)是Walsh 等[8]人提出的基于在线获取的网络诱导传输误差和动态分配网络带宽的调度算法。

Otanez 等[9]人提出的基于死区的动态调度在确保系统性能的基础上动态地丢弃一定比率的数据，以减轻网络的负荷。但是当多个获准访问网络的数据包同时竞争网络资源时，该策略不能确定数据包发送的优先级。

基于业务平滑的动态调度是Kewon等利用业务平滑的技术控制Ethernet网的通信量，通过在Ethernet 网的UDP( TCP/ IP) 层和MAC 层插入定速率业务平滑器和自适应业务平滑器以限定MAC 层数据包的到达速率，并且保证网络诱导时延的有界性，从而提高网络的服务质量.

Cena等提出的优先级提升—分布式优先级排队调度( PP-DPQ)可以保证实时数据传输最大间隔具有确定上界，非实时数据在传输中公平地竞争网络资源。

基于时间窗的动态调度（Dynamic Time Window）是Raja对基于时间窗的静态调度算法进行改进，提出优先级循环服务和动态时间窗的带宽分配策略。

模糊动态调度是白涛[13]等将模糊控制理论引入到NCS 信息调度中，利用基于IF2THEN 规则的模糊逻辑确定数据传输的优先级。

3.1.3　混合调度

Zuberi等针对CAN 下网络控制系统，提出混合通信调度(MTS)策略。在设计调度策略时，考虑到数据实时性要求不同，可以分别采用不同的调度策略，以提高网络资源的可调度性。Tabuada等[27]给出的退火控制任务的事件触发实时调度是基于有反馈事例的事件触发调度器，并且给出了它如何保证系统性能的条件。

3.2　调度与控制的协同设计

目前关于控制与调度共同设计成为研究热点受到越来越多的重视，大体可分为开环调度和反馈控制实时调度两方面。

3.2.1　开环调度

1）对NCS 中各个控制环中数据传输节点采样周期和采样时刻的调度

Hong基于“窗口”的概念，给出了一种通过调度采样时间来减少时延的影响并提高网络利用率的调度算法，建立了NCS 控制系统性能与网络性能间的约束关系。但该算法是基于令牌环系统(token passing system) 和轮询系统(polling system) 的一维对象的调度，系统中信息类型仅限于周期性信息。Kim等[16 ]基于相同思想提出了适用于多维对象的采样时间调度算法。刘鲁源等[17 ]提出了利用剩余的时间窗口调度非实时数据提高了网络资源利用率的调度算法。

2）调度优化

Seto[19] 针对性能指标是单调递减并且是每一任务频率的凸函数的这样一类控制系统，提出了一种通过改变采样频率使得任务能被EDF和RM调度的新算法，而且系统的性能在有限计算资源的约束下可达到最优。但该算法没有考虑执行时间的变化与扰动问题。Cervin[20]考虑了具有时延变化的控制系统采样周期的选择问题，对低于一个采样周期的时延系统的采样周期进行了分析。Ryu 等[21] 以稳定状态误差、过冲、上升时间、沉降速度等作为控制性能参数，并将它们表示为采样周期和输入输出延时的函数，在可调度约束条件下用迭代算法对这些性能参数进行优化。何坚强等[24 ] 在上述研究的基础上给出了NCS 的优化模型并采用遗传算法来求取采样频率。Branicky 和Zhang 等[25 ]提出将非抢占RM调度算法应用于网络控制系统的调度，并给出了保证系统稳定和网络可调度的充分条件。在此基础上，Branicky等[26]进一步对网络传输时间进行了分配，给出了网络调度优化方法。

3.2.2 反馈控制实时调度

开环调度算法在负载能精确建模的动态或静态系统中可以取得很好的效果，可是在不可测的动态系统中，算法的有效性要极大地降低。近几年来，“闭环”调度由于可以应用于很多实时领域因而引起了很多人的关注。在Seto等提出的系统控制和调度离线集成设计的基础上，Cervin[14]提出一种将控制和调度动态弹性集成的框架，允许在线平衡控制性能和可用的计算资源。Stankovic等[18]提出了反馈控制实时调度的思想，而且还给出了一种结合PID 控制和EDF 调度器的反馈控制实时调度算法FC-EDF ( Feedback Control- Earliest Deadline First) 。汤贤铭等[2]提出了一种将动态死区控制和优先级分配相结合的反馈调度策略，用以解决在工作负载变动的环境中网络控制系统的控制与调度问题。Eker等[15]开发出了针对线性二次(Linear Quadratic) 控制的反馈控制器。在可调度的情况下通过调整控制环频率来优化控制性能。Zhao[28]提出了一种结合速率单调调度和新的动态调度的动态反馈调度，用于调度预控制器产生的控制信号的传输，该调度算法确保了系统的稳定性，并且保证系统时延不超过保证系统稳定的上限。

4 进一步可研究的参考方向

当前，NCS信息调度的研究已经取得了很多有益的成果。然而，NCS应用的复杂化以及NCS控制与调度的协调设计趋势，使得现有的信息调度方法已不能满足发展的需求。因此，给出信息调度的进一步研究问题和研究目标，以供参考。

（1）网络控制的复杂化和网络运行状况的多变性，需要智能化强、实时性好的在线调度算法。

（2）现有的研究结果大多限于单控制回路，对共享网络的多个控制回路的优化调度等问题需要进一步的研究。

（3）有带宽约束的变速率网络化控制系统的信息调度问题。

（4）不同数据流分配不同比例带宽，用来提高高优先级别数据流的服务质量，避免低优先级别的数据流由于网络超时而断开的研究。

（5）研究NCS 多目标优化问题的提取和求解。考虑网络利用率、数据包丢失率、系统稳定性等多重约束，建立NCS 多目标优化问题的数学模型。进而考虑NCS 的实时性要求，研究基于遗传算法等进化智能计算方法的NCS 分级多目标优化问题的求解方法。

（6）将系统性能的优化映射为较低层次的系统参数优化、网络参数选取、带宽资源调度问题，力求达到系统设计与网络实现的总体性能优化的目标。引入新的、更多的反映系统性能的优化指标，寻求新的融合网络与控制系统其它结合点将是未来的发展方向。

参考文献

[1] 洪艳伟，赖娟，杨斌.基于EDF 算法的可行性判定及实现.计算机技术与发展[J].2006，16(11)：97-102

[2] 汤贤铭，钱凯，俞金寿.网络控制系统动态死区反馈调度.华东理工大学学报[J].2007，33(5)：716-721

[3] 张庆灵，邱占芝.网络控制系统[M].北京市：科学出版社，2007.37-38

[4] 文远保，张炫.单调比率调度算法研究及改进.计算机工程与科学[J].2006，28(10)，68-70

[5] 叶明，罗克露，陈慧. 单调比率(RM)调度算法及应用.计算机应用[J].2005，25(4)：889-891

[6] LIU Luyuan，WAN Renjun，LI Bing. On static scheduling algorithm for networked control based on TTCAN protocol .Control and Decision[J ].2004，19 (7)： 814 - 816

[7] 张奇智，曹春生，张卫东.EDF 调度方法在交换式工业以太网中的实现.化工自动化及仪表[J]. 2004，31 (6)：41-43

[8] Walsh G C，Hong Ye. Scheduling of networked control systems . IEEE Control System Magazine[J].2001，21 (1)： 57 - 65

[9] Otanez P，Moyne J，Tilbury D. Using deadbands to reduce communication in networked control systems [A].The American Automatic Control Council[C]. Anchorage：Proceedings of the American control conference. 2002：615-619

[10] 刘怀，费树岷.基于EDF的分布式控制系统容错调度算法.软件学报[J].2003，14(8)1371-1378

[11] 张惠娟，周利华.一种基于EDF算法的多处理器实时调度算法.计算机工程与应用[J].2003，30(16)16-17

[12] 王智. 面向现场总线的分布式实时系统的建模与分析方法[D]. 博士，中国科学院，2000

[13] 白涛. 网络控制系统的性能分析与调度优化[D] . 硕士，上海交通大学，2005

[14] ARZEN K E，CERVIN A，EKER J . An introduction to control and scheduling co-design[A].In Proceedings of the 39th IEEE Conference on Decision and Control [C]Sydney： 2000，4865 - 4870

[15] EKER J，HAGANDER P，ARZEN K E. A feedback scheduler for real-time controller tasks. Control Engineering Practice[J].2000，8(12)：1369 -1378

[16] KIM Y H，PARK H S，KWON W H.A scheduling method for network based control systems[A]. In Proceedings of IEEE ACC[C].USA，1998：718 - 722

[17] 刘鲁源，万仁君，李斌. 基于TTCAN 协议的网络控制系统静态调度算法的研究.控制与决策 [J].2004，19(7)：813 - 816

[18] STANKOVIC J A，LU C Y，SON S H，et al . The case for feedback control real-time scheduling[A]. In Proceedings of the 11th Euromicro Conference on Real-Time Systems[C]. New York：1999，1：11 - 20

[19] SETO D，LEHOCZKYJ P，SHAL. Task period selection and schedulability in real-time systems[A]. In Proceedings of the 19th IEEE Real-time Systems Symposium[C]. Madrid，1998：188 - 198

[20] CERVIN A. Integrated control and real-time scheduling[D]. Ph. D. Dissertation，Department of Automatic Control Lund Institute of Technology，2003

[21] RYU M，HONG S. Toward automatic synthesis of schedulable real-time controllers. Integrated Computer aided Engineering[J].1998，5(3)：261 - 277

[22] TINDELL K，BUMS A. Analysis of Hard Real-time Communication. Real-Time System[J].1995，9(2)：147 - 173

[23] LEHOCZKYJ，SHAL，DING Y. The rate monotonic scheduling algorithm：exact characterization and average case behavior[A]. In Proceedings of IEEEReal-time Systems Symposium[C].Santa Monica：1989：166 - 171

[24] HE J Q，ZHANG H C，JING Y Z. A integrated control and scheduling optimization method of networked control systems. Journal of Electronic Science and Technology of China[J].2004，2(2)：56 - 59

[25] ZHANG W，BRANICKYM S，PHILIPS S M. Stability of networked control systems. IEEE Control Magazine[J].2001，21 (1)：84 - 99

[26] BRANICKYM S，PHILLIPS S M，ZHAN GW. Scheduling and feedbackcodesign for networked control systems. In Proceedings of IEEE Conference on Decision and Coutrol .Las Vegas[J].2002：1211 - 1217

篇8

论文摘要：运用虚拟现实仿真 (VRS)进行实验教学是激发学生学习兴趣的有效途径。针对大学生的学习特点，分析了传统教学方法的不足，探讨了基于虚拟现实仿真的“生产与运作管理”实验教学的特点、内容和形式，有助于高校教师优化教学过程，提高教学质量和教学效果。

纵观我国工商管理本科专业人才的就业去向可以发现，毕业生就业去向大都是金融业、政府机关和高校，极少有人自愿去制造企业工作，即使到了制造企业，也只愿意去财务或营销部门，而不愿去生产管理部门，原因是生产管理部门的岗位工作环境较差，待遇较低，付出多，导致集中了企业绝大部分财力、人力、设备及其他资源的生产系统受到冷落。在这样的人才使用环境中，学生对于与生产管理相关的课程自然就不重视。然而，从工业发达国家看，近年来，纷纷将注意力转移到生产领域，企业界和学术界也都开始重新审视企业内部的生产系统及其管理理论，将生产战略问题作为企业经营战略的重要组成部分来研究。可见，创新教学方法，增强学生学习 “生产与运作管理”课程的兴趣，具有非常重要的现实意义。

1 生产与运作管理课程的教学调查和教学方式的分析

1．1 教学调查

在浙江省精品课程 “生产与运作管理”的建设过程中，为了有针对性地开展课程教学方法改革，我们就本课程的学习，于2007年对我校 04级工商管理专业40名学生做了一次调查，得到如下结论：

(1)由于学生没有实际工程背景，缺乏对企业生产与运作管理的感性认识，对于生产与运作管理的一些理论和方法理解有一定困难；

(2)学生对生产与运作管理课程的认识存在误区，对相关理论知识掌握不熟练，对未来是否从事生产管理工作信心不足，导致学习该课程的动力不足：

(3)随着非制造业在国民经济中地位的提升以及制造业和非制造业现实的工作性质、工作环境和条件、工资待遇等方面的差异，决定了学生对以制造业为主体的生产与运作管理课程热情不高；

(4)学生对传统的案例讨论、观看录像、企业参观、专家讲座、计算机辅助教学等教学模式基本认可，但是对创新教学方法和手段的需求更为强烈。

1．2 教学方式分析

生产与运作管理是一门实践性、操作性强的课程，教学 的关键是让学生产生 “真实感”。教学方式除了课堂授课外 ，传统的教学方式主要有如下几种 。

(1)观看录像。这种方式比较简单，国外教材都配有相应的录像教学光盘，学生通过观看录像了解国外先进企业的生产与运作管理经验。比如针对质量管理专题，播放美国著名酒店的全面质量管理录像；讲授 5s现场管理，播放一盘有关现场改善的录像；讲到供应链管理、库存管理时，根据需要选择相应的录像播放。

观看录像这种方式存在 2个问题，一是现有录像大多是英文版，录像的对话比较快，多数学生听不清楚。另外，录像内容以综合性为主，缺乏针对国内生产管理的专题教学光盘。

(2)参观企业。这是一种比较好的理论联系实践的学习方法，能够让学生真实感受到企业的实际生产隋景，并对照所学的专业理论知识加以思考。比如，针对绍兴纺织特色，选择了纺织印染企业作为参观对象，让学生到生产车间看设备布局、生产流程、生产计划与调度、质量控制、现场改善与员工的班组建设等基层运作管理。

这种方法在实施中存在困难，主要是没有建立固定的教学基地，与企业没有稳定的关系；而且，随着学生人数的逐年增多，许多企业对学生参观不感兴趣。

(3)邀请企业专家讲座。对于某些实务性、技巧性比较强的内容，如生产调度、员工指派、班组建设、现场改善等，请企业专家结合自己的工作实际，现身传授管理技巧和经验，比任课教师讲效果好，印象深。

与参观一样，邀请专家也存在一定困难。由于企业的工作繁忙，很难保证企业专家能按照课程的教学时间来安排讲座，这样很有可能打乱教学计划。

(4)案例讨论。教学案例一方面可以增加学生的实践知识，另一方面帮助学生深入理解相应的教学内容，提高学生分析问题、解决问题的综合能力。生产与运作管理课程案例不同于其他管理课程的案例，它的特点是需要生产与运作管理理论知识作基础解决实际问题。比如：生产能力规划案例只有在学习完生产能力查定办法相关理论的基础上，才能进行案例分析；库存管理案例的中心是解决库存问题，如果不了解库存管理理论，是很难进行案例讨论的；又比如网络计划案例，在讨论的时候，学生首先要对网络计划技术有所了解，然后才能进行案例分析。

目前好的生产与运作管理案例不多，主要问题是：案例篇幅太长，描述性内容多，真正反映生产与运作管理的实际数据和实际场景模拟少，教学效果不佳。

(5)传统的计算机辅助模拟实验教学系统(实验教学软件)。采用计算机和多媒体辅助实验教学，教师可以精心设计教学内容，使复杂问题简单化，繁琐问题条理化，抽象问题具体化，具体问题概括化，使教学过程以直观的形式达到人机一体，便于围绕某一学习主题进行密集、快速的活动，同时增加了课堂教学的密度和广度。目前本课程中常用的实验软件主要有物料需求计划／制造资源计划实验 (MRP／MRP II)、项 目进度计划实验 (PERT)、质量管理实验 (排列图、因果图、直方图、控制图)、工作分析与工作研究实验等。

从近年来的实施情况看，学生对这种传统的计算机辅助实验教学开始产生视觉疲劳，兴趣逐步减弱。原因在于某些实验教学软件只是教学形式的变化，更多的是将重点放在了生产与运作管理活动教学模型的求解上，而对于更为重要的企业业务流程分析、经济模型构建与咨询诊断等功能没有真正体现。实验过程中，学生只要记住几个参数，并输入到软件规定的相应位置，就可以得出实验结果，不能真正起到培养学生知识运用能力和创新能力的目的。另一个主要原因是该课程实践性很强，而高校教师普遍缺乏企业生产管理的实际经验。某些教师一直从事教学工作，没有企业的从业经历，或者即使有一定的生产管理的实际经验，也由于长期在高校从事教学和学术研究，对企业目前生产运营中的某些实际问题的了解不够深人。由于实际管理经验的缺乏，教师容易在教学中造成理论和实践脱节、枯燥和不生动等问题。

2 虚拟现实仿真技术在“生产与运作管理”教学中的应用

随着管理思想的发展和新技术、新方法、新成果的不断涌现，生产与运作管理学科的范围和内容在不断拓展，仅仅依靠人的经验及传统的计算机技术难于满足越来越高的要求。基于现代计算机技术及网络的虚拟现实仿真技术，已经广泛应用于电力、交通运输、通信、化工、核能等各个领域。借助虚拟现实仿真技术进行本课程的实验教学，对企业业务活动进行多维仿真，给学生产生各种感官信号，使学生有身临其境的感觉，并能使学生与虚拟现实环境之间进行多维信息的交互，从定性和定量结合集成的虚拟环境中获得企业生产运作活动的感性和理性认识，体验、接受和认识客观事物，深化对概念、原理和方法的理解，进而提出设计创意。在制造业生产系统的规划、设计、运行、分析及改造的整个生命周期，都可以使用虚拟现实仿真技术进行实验教学，具有代表性的主要有如下几种。

(1)用于产品研发的仿真实验。产品研发过程可分为概念设计、细节设计、评审和再设计阶段。每一阶段又可以细分，如详细设计可分为总体CAD、零部件 CAD、计算机辅助工程、可制造技术、可装配性设计等。产品研发过程的仿真实验就是对上述活动进行模拟，让学生从进度、资源和成本等指标进行综合分析，选择集成的最优方案。

(2)用于车间设施规划和布局的仿真实验。根据车间之间和车间内部空间的组织方式，采用虚拟现实仿真技术模拟各种方案，判断车间整体布局是否能满足车间调度要求，车间设备是否得到充分利用，负荷是否比较平衡，物料处理系统是否能够和车间的柔性程度相适应，生产制造运输费用是否合理等。例如在流水线生产系统的仿真实验中，运用WITNESS仿真软件模拟流水生产过程，加深学生对流水线组织设计与技术设计的理解和掌握，让学生学会对流水线进行控制。目前国内外用于辅助车间生产系统设计的仿真软件有 PURDUE大学开发的 GCMS，System Modeling公 司开 发的 SIMAN／CINEMA，Auto Simulation公司开发的 AUTOMOD／AUTOGRAM和清华大学开发的 IMMS等。

(3)用于车间生产调度的仿真实验。车间内部的生产调度问题包括：确定工件的加工路线，确定工件在机器上的加工工艺和加工时间，选择运输路线和工具，指派加工工人等。生产调度仿真实验就是对这些调度问题进行分析和评价，目前已经有一些成熟的软件可用来仿真调度问题，如 Autosched、JobTimePlus、FACTOR、FACTOR／AIM和 SIMNETD等。我国也已研制开发了用于车间调度层面的仿真软件，如南开大学研制的JobShop，清华大学与航天部204所等单位开发的工厂仿真调度环境FASE，以及在此基础上开发的智能规划调度系统等。

(4)用于物流与供应链管理的仿真实验。从生产线到车问到整个工厂，再到供应链系统的库存、瓶颈、流程、协作和信息共享等方面，通过仿真可以快速改变和优化系统的流程逻辑和决策数据的灵敏度分析。如：在物流系统中配送路线的优化实验中，运用 WITNESS软件的设计功能，根据规划与物流分析的主要内容，以物流系统中运输成本最小为目标，设计物流系统中的配送路线，使整个配送路线最优，从而达到运输成本最低；在垃圾回收物流仿真系统设计实验中，仿真程序研究如何设计物流系统，使收集系统在满足时间约束、载重约束的条件下，使垃圾处理公司的物流总成本最低。系统涉及的指标主要有车辆载重量、随车工作人员数和客户满意度。

总之，虚拟现实仿真技术在制造业的应用已经贯穿于产品设计开发、生产计划制定、加工、装配、测试和销售的整个生命周期。

除了上述单一企业的生产管理的虚拟现实仿真技术外，用于虚拟企业业务流程集成的虚拟现实仿真技术正成为仿真技术研究的热点。比较典型的仿真实验软件是 CIM—OSA，在应用 CIM—OSA进行供应链分析与设计时，系统描述了2个仿真工具的开发和设计。其一是在 Arena仿真平台上开发的单机后勤仿真器，其二是基于 Internet的虚拟企业内供应链集成仿真环境。在基于 Internet仿真器的功能设计上，每个供应链模块包括在线的Intemet应用和离线的信息管理 2个模块。Intemet系统在通用的www环境下进行开发，以支持各类广泛应用的Web服务器和浏览器。根据不同供应链伙伴的不同需求，如在线订购和在线库存量检索等，它们的应用系统将有所不同。

另外，虚拟现实仿真技术的应用也正在向服务业不断渗透。目前许多高校在生产与运作管理的实验课程中，都安排了服务业的相关仿真实验，代表性的是采用 Lanner公司提供的世界领先的仿真工具 WITNESS。通过 WITNESS对实际商业系统 (工业工程、制造工程、运作管理、供应链与物流、战略管理、业务流程)的建模和仿真，让学生了解不同制造业、服务业的运作流程。通过 WITNESS模型的交互菜单，学生可以作出不同的管理、运作流程项目的设计，并能够及时运行和获得系统的效果，给学生提供深刻的流程体验，使学生能很好地完成生产与运作管理课程的各项设计任务，达到真正提高教学效果的目的。

3 结束语

生产与运作管理是一门实践性很强的课程，从增加现实场景模拟、加强课堂师生互动、强化理论与实际结合等方面不断创新多样化的教学方法，对学生进行实践技能和科学研究方法的训练，不仅有助于学生巩固课堂所学知识，加深对生产与运作管理基本概念、基本原理和分析方法的理解，掌握从事企业生产与运作管理活动的基本技能，而且，能够拓宽学生的知识领域，锻炼学生的实践技能，培养科学严谨、求真务实的工作作风。

参考文献（References)：

[1]王晓燕．案例教学法在管理类本科教学中的应用研究 [J]．武汉科技大学学报：社会科学版，2007，9(4)：412．414．

[2]陈志祥．MBA《生产与运作管理》课程建设与教学方法研究[J]．教育与现代化，2006(3)：3．8．

[3]许志端．《生产与运作管理》教学中企业参观的课程设计[J]．厦门大学学报：自然科学 版，2003，42 (10S)：144—147．

[4]王亚超，马汉武．生产物流系统建模与仿真 [M]．北京：科学出版社，2006．

篇9

目前国内物流公司的出厂装箱调度仍旧采取效率极低的人工调度，尽管国内外二维、三维装箱调度问题已经有大量研究，但由于国内绝大部分物流公司不够规范，而采用二维、三维装箱调度对人员素质要求较高、统计难度较大，同时对公司的信息系统有较高的要求，先进的理论在实践中没有得到很好的应用，因此本文从整车订单和轿运车配载的过程，不考虑整车目的地和轿运车的路径选择，抽象出带装载组合约束的一维装车问题，即有n个属于l种类型的相同（单位）尺寸的物品。有w辆车，每辆车对这l种类型的物品有几种装载组合，不同车辆的装载组合不同，每辆车选择一种装载组合并严格按照物品组合进行装载。优化目标是在满载的情况下装载最多的物品，同时给出每个物品的具体配载方案。如：有10个属于3种类型的物品，每个物品的类型见表1；有2辆车，车辆1有2种装载组合，车辆2有3种装载组合，装载组合见表2。显然当选择车辆1的装载组合2，车辆2的装载组合3时，两辆车都能满载且能全部装完所有10个物品，是最优解。

本文假设车辆资源的节约价值不大，因此将装载最多的物品作为优化目标。同时，定义满载率来表示车辆的利用率，满载率为当次调运装载的所有物品数与参与调运的所有车辆装载总量之和的比例，本文将满载率设置为100％。带装载组合约束的一维装车问题是由实践研究中提炼而成的理论模型，相似的问题为有色装箱问题［1］，后被广泛应用于多处理器任务调度［2］、并行处理［3］以及多媒体存储［4］等问题。Shachnai提出有类型约束的装箱问题［5］。其他一维装箱问题的衍生问题有：杨鼎强［6］提出受位置约束的有色装箱问题，Epstein研究了有类型约束的覆盖问题［7］，Xavier提出有类型约束的货架装箱问题［8］，Marques提出有分区的背包问题［9］。Hoto给出了分区背包问题的材料切割实例［10］。本文从精确算法和启发式算法两个方面入手，首先建立线性混合整数规划模型得出问题的精确解，并根据问题的特性利用贪婪技术建立近似算法模型，最后进行数值实验和参数的敏感性分析。本文试图提出针对特定场景下的出厂物流调度问题的有效算法，并给出合适的参数设置，从而提高整车出厂物流调度的速度与准确性。本文结构如下：第1节描述问题并建立线性混合整数规划模型，第2节建立基于贪婪算法的启发式算法，第3节数值实验与敏感性分析，第4节是本文的结论与进一步研究的展望。

2　问题描述及数学建模

2．1　问题假设本文所研究问题的假设有：（1）所有物品尺寸为1单位；（2）每辆车以及不同车的装载组合是独立的；在实际调度中可能存在两辆车的装载组合相同，但考虑到每辆车除了本文提及的信息，还有所归属的运输公司、调运目的地偏好等的不同，因此认为这两个装载组合也是不同的。（3）所有参与装载的装载组合都必须满载。

2．2　问题描述本文研究的带装载组合约束的一维装车问题描述为：物品数m，物品集合I＝｛1，2，…，m｝；物品的类型为mi，类型数集合K＝｛1，2，…，l｝，车辆数w，单位的装载容量，每辆车只能选用一种装载组合，并严格按照装载组合装载物品。优化目标是在满载的情况下装载最多的物品。

2．3　复杂性分析考虑带装载组合约束的一维装车问题的简化问题，当每辆车只有一个装载组合时，问题变为：有l种类型的物品，类型k的物品数Qk，有n个装载组合，第j个装载组合对类型k物品的容量Cjk，对所有类型物品的容量Cj，选择装载组合以尽可能装载最多的物品。已知多维背包问题为NP－难问题［11］，多维背包问题是从给定选项的集合I＝｛1，2，…，n｝中选出一组满足所有约束的项，使其价值之和最大，数学公式为其中，pj为项j的价值，令pj＝cj；xj为对应项j的变量，项j被选中xj＝0，否则，xj＝0；rkj＞0为项j的消耗资源k的量，令rjk＝Cjk；bk为资源k的总量，令bk＝Qk，Qk为第k种类型的物品数。此时多维背包问题转化为一维组合装车问题的简化问题，则一维组合装车问题的简化问题为NP－难问题，显然一维组合装车问题更为复杂，也即一维组合装车问题为NP－难问题。

2．4　线性混合整数规划模型本文的最终结果是给出具体的装载方案，即物品装载在哪辆车的哪个装载组合上，因此以物品作为决策主体，物品选择车辆、装载组合。其他参数与变量如下。参数m：物品数；l：类型数；w：车辆数；v＿n：第v辆车的装载组合数，j＝1，2，…，v＿n；Cvjk：第v辆车第j个装载组合装载第k种类型物品的容量。变量xivj：1，若物品i装在车辆v的第j个装载组合上，否则为0；yvj：1，若车辆v选择第j个装载组合，否则为0。数学模型基于上述定义，建立如下线性混合整数规划模型。　优化目标为物品装载数最多；约束式（1）表示一辆车最多只能选择一种装载组合；约束式（2）表示一个物品最多只能被装载到一辆车的某个装载组合上；约束式（3）表示每辆车必须严格按照装载组合装满每种类型的物品；式（4）、式（5）定义了变量的取值范围。

3　启发式算法

鉴于问题的NP－难特性，问题规模变得很大时，利用线性混合整数规划求解问题的精确解将变得非常困难。因此，本节采用贪婪技术提出快速有效地求解该模型的近似算法。构造贪婪算法的基本迭代思想是：每一次迭代，仅选择当前状态下迭代一步时得到的最好解，该方法不考虑迭代二步以上情况下的最优解。当算法迭代达到停止准则时，算法停止，产生近似解［12］。贪婪算法被成功应用于背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树等最优化问题的求解。在车辆的装载组合选择阶段忽略每辆车只能选择一个装载组合的约束，每辆车的每个装载组合都进入筛选。第一阶段，筛选阶段。每一次迭代都将每个类型的物品分配到其装载能力最高的装载组合中，当所有类型的物品都分配完时该轮筛选结束。第二阶段，车辆选择阶段，如果某辆车装载组合满载，则选择装载总量最大的一个装载组合。循环第一、二阶段，直到所有车辆用完或剩余物品不能使任一剩余车辆的任一装载组合满载。最后采用最先满足方法将选出的车辆装满相应类型的物品。最先满足方法是指在搜索过程中，选择最先遇到的满足条件的物品。基于同类型物品无差异的假设，本文选择依据为物品的类型。终止条件：所有车辆用完或剩余物品不能使任一剩余车辆的任一装载组合满载。贪婪准则：选择当前可用车辆的可用装载组合装载量最大的装载组合。可用车辆是指在未满载车辆组合中，可用装载组合指对某种类型的装载容量大于0且小于等于该类型未分配物品数。宽恕机制：当出现某辆车的某个装载组合多数类型的容量已满足，未分配物品中存在可以使该装载组合满载的物品类型，则选择未满载类型数最少的车辆。显然当全部车辆都能满载时总装载物品数最多，贪婪准则导致部分车辆因某种类型物品装载量较低而不被选择，设立宽恕机制可以提高车辆利用率。骤1；如所有装载组合均不满载，下一步。步骤4：找出所有存在某种类型的容量已满足的装载组合，且未分配物品中存在可以使该装载组合满载的物品类型，如果存在，则选择未满载类型数最少或装载总量最大的车辆，将其放入VO，装入的物品放入IO。将不在VO中的所有车辆的装载组合的每个类型标记为可用，返回步骤1；否则，算法结束。步骤5：计算满载车辆数，装载物品数。

4　数值实验与敏感性分析

本文在嵌入64位ILOG　Cplex12．2插件的Visual　Studio2008平台上采用C＃语言编写混合整数规划和启发式算法的程序软件，并进行各项实验。

4．1　数值实验问题规模由物品数n、物品类型数l、车辆数w、每辆车的装载组合数j＿n等因素决定。根据实践应用的需求，设置装载组合数区间为［5，10］，装载总容量区间［8，12］，类型数为6，物品与车辆比例为10，根据物品、车辆数不同规模，设置了10组实验，分别测试混合整数规划模型和启发式算法的求解精度与速度。详细实验参数设置如表3所示，实验数据为该参数设置下生成的随机数据，每组实验生成50份数据，所生成的输入数据如表4。

为在可接受的时间内得出可接受准确率范围内的结果，本文在求解程序中设置Gap值5％，求解时间1800秒。实验结果数据为具体的装载方案，除了装载物品总数和使用车辆数，也给出了哪些车辆的哪个装载组合装载的物品编号，如表5表示车辆2采用第5种装载组合装载物品67、107、116、176、179、181、227和232。统计结果数据时去掉第1份和第50份数据以避免干扰因素，每组算例给出了均值、最优值和最差值，表6为算法的结果统计数据。

本文采用三个指标来评价算法：求解结果与最优值之间的比值，用Gap表示，Gap＝（最优值－目标函数值）／最优值，最优值通过ILOG　Cplex获取，为模型获得目标函数值时的最优值；车辆利用率＝求解结果中车辆使用数／输入数据中车辆数；程序运行时间。分别绘制混合整数规划算法和启发式算法Gap值、求解时间的平均值对比图，见图1。对比混合整数规划算法与启发式算法的结果，可以发现，基于贪婪技术的近似算法在运行速度上有绝对的优势，但求解结果较最优化算法较差，车辆利用率较低。

4．2　敏感性分析分析数值实验结果，可以发现车辆使用率平均值不足90％。原因为每辆车必须严格按照装载组合满载装运，装载组合是制约车辆使用率的关键因素，同时车辆装载组合数也是影响问题规模的因素之一，因此测试装载组合数对车辆使用率与运行时间的影响很有意义。选用500个分属于6个不同种类的物品，50辆车分别进行装载组合数为5、10、15、20、25、30的数值实验。基于实际应用中资源（时间、程序运行内存等）的限制，测试选用精确算法模型并设置Gap值5％，求解时间1800秒。记录测试的平均Gap值车辆利用率、运行时间，利用表7中平均车辆利用率和平均运行时间，绘制每辆车的装载组合数与运行时间关系和车辆利用率关系图2，可以看出车辆利用率随着装载组合数增加而提高，在每辆车15－2个时，车辆利用率达到峰值，之后缓慢下降。这是因为装载组合数增多求解难度加大，在有限的时间内更难得出最优解，达到5％Gap需要更长的时间，此时模型求解时间呈指数型增长。

影响问题规模的其他因素还有物品数、车辆数、类型数，其中类型数是算法内置参数，类型数设置的好坏不仅影响物品调度的优化程度，也是影响算法难解性的重要参数。研究类型数与求解时间的关系，对实际应用有很好的指导意义。测试物品数500，车辆数50，每辆车装载组合数10，每个装载组合装载总量［8，12］，表8记录物品类型分别为3、6、9、12、15、18时的运行时间，并用其平均情况、最好情况、最差情况以及物品平均装载数绘制图3。由图3可以看出，随着类型数的增加求解时间消耗降低，同时物品装载数也迅速减少。在实际应用中需结合实际物品特性与时间消耗、求解精度来合理设置物品的类型数。

篇10

［关键词］ 供应链； 能力分配； 多级制造； 约束满足

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 18. 044

［中图分类号］ F273 ［文献标识码］ A ［文章编号］ 1673 - 0194（2012）18- 0078- 03

1 引 言

现代的市场竞争已经不仅仅是企业与企业之间的竞争，更是供应链之间的竞争。市场的瞬息万变使得企业面临着更大的挑战，要想在激烈的竞争中处于不败之地，供应链的整合便显得尤为重要。早在2000年，马士华［1］便论述了核心企业在供应链运作中的地位，探讨在供应链企业间形成战略伙伴关系过程中，处于主导地位的企业所起的作用及其影响因素。而供应链整合［2］是企业有效拓展外部资源、实现运作效率提升与综合发展的主导方向之一。但长期以来，该整合过程普遍受制于“如何合理处理客户服务满意水平、资源整合成本与系统整合后运营收益三者之间的悖论关系”，探索如何对复杂的供应链进行合理高效地整合、运作与监控，在满足客户个性化需求水平前提下实现供应链系统各成员的当前与长远收益是一个必须解决的课题。

国内外很多学者就供应链集成建模和优化问题进行了研究。Pinar和Bulent［3］针对单种产品、多供应商、多生产商、多分销商的三级产销问题给出了混合整数模型。Chiung Moon［4］等就多工厂供应链系统的集成工艺规划与调度问题以总延迟最小化为目标建立了数学模型，并设计了一种基于启发式方法的遗传算法进行求解。姬小利［5］建立了面向供应链的多产品、多订单、多时段的订单任务分配的混合整数线性规划模型，并设计了基于遗传算法和启发式规则相结合的混合遗传算法进行求解。向晋乾［6］等以集团利润最大化为目标，运用优化理论建立了单目标0－1规划的订单分配模型并举例说明模型的求解。朱宝琳［7］等针对供应链中分散独立的实体，利用市场价格和中间库存因素使供应链上下游企业结合成一个整体并建立一个供应链一体化计划模型，采用拉格朗日松弛技术对模型进行求解。郭永辉［8］以面向订单的制造模式为主要研究对象，采用集中式规划思想，提出一套基于瓶颈思想的供应链产能规划方法。吴学静［9］等研究了带软时间窗的分批配送问题及其对需求分配与生产调度的影响，以运作成本最小化为目标建立了数学模型，并设计了协同进化粒子群优化算法并进行求解。齐二石［10］等基于对复杂零件制造的工艺流程的研究，提出了以工艺流程为核心的制造资源优化配置模型，并最终将资源优化配置问题归结为多目标优化问题，并利用遗传算法进行求解。

现有研究很少关注在采购—生产—分销的供应链模型中的生产环节中上下游制造商之间资源的具体分配情况。而在现实生产中，在整个生产体系中上下游制造商之间往往会是多对多的关系，而且由于运输成本，各制造商的差异性等原因，在上下游制造商之间会出现优先级的关系。本文对带有多级制造商的供应链（Supply Chain with Multi－stage Manufacture， SC－MM）资源配置方法进行研究，应用约束满足技术进行求解，并通过仿真实验和应用案例对模型和算法进行验证。

2 问题模型

2．1 模型描述

在图1所示系统中存在多级的制造商，其中每一级的制造商所制造的产品均为下一级的制造商准备，包括第一级的供应商在内，相邻的两级的供应商或制造商之间的供给存在一个多对多的关系，而且每一个制造商所对应的上游供应商或制造商的集合中存在优先级的关系。本文根据此类供应链的特点建立数学模型，在分销商产品需求一定的情况下，优化每一级中各个供应商或制造商对于其下游制造商的资源配置情况，从而使整个供应链体系的产品利润最大化、合同饱和度最大化以及产能利用率最大化。

2．2 符号定义

2.2.1 索引

m 最终产品制造商，共有M个最终产品制造商，1 ≤ m ≤ M；

im 第m个最终产品制造商制造的最终产品品种，共有I种最终产品，1 ≤ im ≤ I；

j 最终产品品种，共有I种最终产品，1 ≤ j ≤ I；

l 分销商，共有L个分销商，1 ≤ l ≤ L；

n 多级供应链体系第n级，共有N级，1 ≤ n ≤ N；

nd 多级供应链体系中第n级中第d个企业，总共Dn有个，1 ≤ d ≤ Dn；

p 产品品种（包括最终产品），共有P种产品，1 ≤ p ≤ P。

2.2.2 变量

其中，目标函数（1）表示最大化产品利润；约束（2）表示产品在分销商的最大供给量约束；约束（3）表示供应商或制造商供应或生产的最大产能约束；约束（4）表示上游供应商或制造商对下游制造商的最大供应量约束；约束（5）表示下游制造商选择上游制造商或供应商的优先级约束；约束（6）表示生产中某企业的上下游关系平衡约束；约束（7）、（8）表示流向变量，其中约束（7）表示若产品p不能生产产品q则没有产品流量，约束（8）表示若产品p能生产产品q则一定有产品流量；约束（9）表示共享资源约束下的某企业生产量的计算公式；约束（10）表示共享资源约束下的某企业得到的分配量的计算公式。同时，在该多级制造供应链中，每一个供应商或制造商只供应一种产品，但是，在同一级中的不同供应商或制造商可能供应的产品相同也可能不同。每个分销商均会需求多个最终产品。