1、基于单件生产模式下的资源调度问题研究【摘要】随着企业越来越关注客户需求，单件产品生产（OKP） 成为本世纪一种新的制造范例。OKP 的高度定制化及其如何快速满足顾客需求是困扰 OKP 企业的难题所在。对资源进行合理的调度与规划可以有效地缩短产品生产周期，为提高企业竞争力提供了借鉴。 【关键词】OKP 调度问题 规划 随着顾客订制产品的不断增多，制造业的重点从大批量生产过渡到小批量生产，最终向单件产品生产（ One-of-a-Kind Production，OKP） 方向发展。单件产品生产（ OKP） 方式已成为制造业未来发展的一种新模式。面向订单生产流程往往很复杂，所需资源种类也很多，企业必须
2、对资源进行合理规划、安排，使得各订单能够在最短时间内完成。 一、资源约束调度问题研究综述 资源受限的项目调度问题（Resource 一 Constrained project Scheduling problem， RCPSP）是运筹学的一个重要分支，该问题具有一系列相互关联的活动， 其中，每一活动以已知延续时间和给定资源需求为特征。资源约束项目调度问题发展到现在已经产生了很多分支，现在先介绍一下其最原始的模型， 即基本资源约束的项目调度问题。 基本资源约束项目调度问题。我们考虑最原始的资源受限项目调度问题，它包含以下的假设： （1）一个单一项目包括许多延续时间已知的活动； （2）每个活动的开
3、始时间依赖于其它一些活动的完成（时序约束） ；（3）在调度期内，资源消耗为常量； （4）资源在每个时段上是有限的，但时段之间是可更新的； （5）资源之间不可替换； （6）活动不可被中断； （7）每种活动只有一种执行模式； 基本资源约束项目调度问题常用的目标函数是最小化项目延续时间。该问题的数学描述如下： 其中： ti活动 i 的开始时间； di活动 i 的延续时间（处理时间） ； si活动 i 的紧后活动集合； rik活动 i 对资源 k 的需求量； bk资源 k 的总可用量； Ati在时间毛处理的活动的集合； m资源种类数目。 活动 1 和 n 是标识项目开始和结束的虚活动。 （1.1）式是
4、目标函数，表示极小化项目总延续时间；（1.2）式是活动之间的时序约束；（1.3）式是资源约束，以确保在任何时段所有活动使用资源 k 的量不超过 k 的可使用量。根据约束条件，我们可以定义项目的时序图 G=（V，H） ，H 是时序约束集合，V 是项目活动集合，G 是有向非循环的。 一个简单的网络描述图如图 1.1 所示。 二、资源约束项目调度问题的类型 RCPSP 从资源约束的角度出发来研究多项目调度问题，充分的体现了企业的实际需求，因而从提出起就受到学者的广泛关注。 （1）按项目数量分为资源约束下单项目调度问题（RCPSP）和资源约束下多项目调度问题（RCMPSP） 。 （2）按调度目标分为最
5、小化项目工期、资源均衡利用、最小化项目运作成本。 （3）按资源分为可更新资源问题、不可更新资源问题两类。 （4）按任务执行的连续性分为抢先式、非抢先式。 三、求解资源约束项目调度问题的算法 求解基本 RCPSP 问题的方法不断发展，种类繁多，这些方法一般可以分为精确算法和启发式算法两大类。 （一）精确算法 精确算法是基于问题的优化目标和约束条件建立等式或不等式，通过求解这一数学模型来求得调度问题的最优解。主要包括运筹学中的整数规划、枚举法及分枝定界法。总的来说，精确算法计算量大，不适合实际应用的大规模问题，但这类算法为启发式算法的提出打下了良好的理论基础。 （二）启发式算法 基于优先规则的启发
6、式算法出现于精确算法之后，主要是为了弥补精确算法效率较低的不足，以适用于大规模的项目调度问题。该算法的基本思想是对项目中共同占用资源的可调度任务以优先级规则排列任务的调度顺序。基于优先规则的启发式算法一般由进度计划生成机制（schedule generation scheme，SGS）和优先规则（priority rule）两部分构成。 四、结语 本文主要以 OKP 企业为研究对象，针对单件生产模式生产过程符合工序复杂、交货期短、资源有限的特点，提出资源调度的重要性以及简单介绍了资源约束调度研究现状、类型和算法，为有效缩短产品生产周期提供了理论上的依据。 参考文献： 1MOHANTY R.P， SIDDIQ M.K. Multiple projectsMultiple resources constrained scheduling：Engineering Costs and Production Economics，1989. 2VALLS V， BALLESTIN F， QUINTANILLA S. A hybrid genetic algorithm for the resource-constrained project scheduling problemJ.2008.
