论文部分内容阅读
[摘要]文章对国家电网备件库的订单调度进行了研究。根据备件库订单调度特点，在对比“先来先服务”的调度算法和基于优先级调度算法的优缺点基础上，提出了无人值守的全自动备件库调度：①出库优先于入库；②基于先来先服务的入库订单调度算法；③基于优先级的出库订单调度算法，大大提高了订单的调度效率。
[关键词]订单调度算法；先来先服务；基于优先级调度
[DOI]1013939/jcnkizgsc201801142
1研究背景
文章针对国家电网备件库的信息化目标——全自动无人值守备件库系统进行研究。无人值守的全自动备件库系统具备如下特点：①各级备件库库存减少到警戒线时能够预警并自动预测各备件的采购量并生成采购单，采购单确认后开始采购；②备件使用单位上报备件需求时，系统根据库存情况、备件需求的紧急情况确定出库单优先级，优先级高的优先满足；③对于库存可以满足的出库单（不需采购），综合考虑各使用单位分布情况和各级备件库的库存情况决定从哪个（或者哪些）备件库出库；④备件入库、出库不需人工干预。
文章研究的国家电网的备品备件库的订单调度算法，其订单特点为种类多、需求变动频繁、实时性强，在此背景下，同时具有很多订单的时候，计划与调度要具有敏捷性，能够解决订单的计划与调度的实时性，高效率地安排这些订单并满足订单需求。本文针对这一问题，首先对多订单的出入库调度进行研究，并提出相应的调度算法；其次，对于备件使用单位的备件需求，根据各级备件库的库存情况，设计调度算法，确定该需求从哪个（些）备件库下出库单。
2备件出入库调度系统
21问题描述
国家电网的库房中的备品、备件支撑整个企业的日常生产，如何保证库房中的备品备件有效地支撑企业的日常生产，成为一个亟待解决的问题。在日常的调度中，当库房中的备品、备件消耗后要及时补充相应物品，以保证生产的正常运行；当需要备品、备件的多个订单同时提交时，要及时响应订单，保证及时高效地完成所有订单需求。根据以上需求，我们将库房的订单调度模型抽象成两部分：订单入库和订单出库，通过相关的调度算法，及时响应各种订单信息。在同时需要进行入库和出库时，优先进行出库操作，当出库单都已经操作完成，或者现有库存已经不足以进行出库时，再进行入库操作。
22基于“先来先服务”的入库订单调度算法
在日常的库房维护中，库房管理员会根据备件库预警信息、日常的订单以及用户的反饋采购相应的备品、备件。当库房管理员采购来备品、备件准备放入库房，调度模型即生成一个入库的订单，并记录备品备件的名称、数量、价格、采购时间等相关的属性。该入库订单提交给库房调度系统，系统依据先来先服务的调度算法，根据订单的提交顺序依次处理，将备品、备件放在库房的相应位置，并做好记录，在系统数据库中更新相关信息。
3基于“先来先服务”的入库订单调度算法表示
步骤1：对采购的备品、备件生成相应的入库订单，并根据订单的实际情况对备品、备件的名称、数量、价格、采购时间的等相关属性进行赋值，然后将订单放入入库订单的等待队列中。
步骤2：对入库订单队列中所有的订单，库房调度系统根据其提交的时间顺序依次进行处理，处理完毕后将该订单从入库订单队列中提出，并在系统中更新相关的数据记录。
步骤3：若队列中仍有订单等待，转向步骤2，否则，转向步骤4。
步骤4：订单全部完成，调度算法结束。
31基于优先级的出库订单调度算法
当用户需要相应的备品、备件时，其会向库房调度系统提交一个出库订单，包含其所需要的备品、备件。库房调度系统会根据其相应的调度算法，及时响应订单，满足用户的需求。在日常的使用中，通常面临两个方面的问题：①备件库无法满足当前订单需求，如何快速有效地通过备件库调度来满足订单需求；②备件库面临提交的多个订单时，如何快速响应订单要求，满足订单需求。如何完善地解决上面两个问题，成为库房调度系统设计成败的关键。
基于优先级的出库订单调度算法主要包括两部分内容：备件库的选调度和出库订单的调度两部分。当用户提交出库订单后，库房调度系统首先根据订单的内容，首先判断对应备件库是否能满足订单需求，若不能满足通过备件库的调度能否满足订单需求。若满足需求后，备件库接收订单，根据出库订单调度算法进行订单的出库。
32备件库调度
国家电网备件库包括不同级别的多个备件库，并且分布在不同的区域。原则上，每个备件库都有其固定的服务范围（使用单位），在备件库的库存允许范围内，各个使用单位的备件需求都由相应的备件库提供。当备件订单需求十分急迫，但是对应的备件库因为备件不足难以提供时，采用优化算法，选择其他备件库，给该备件库生成出库单。选择算法如下：
①寻找那些可以满足本身服务任务基础上，能够额外满足该需求的备件库。
②选择一个代价（运费）最低的备件库。
33订单出库的调度算法
在库房调度系统的多订单调度问题中，最常见的调度模型为先来先服务和最短时间优先服务两种模型。[1]先来先服务调度模型实现最简单，谁先来先处理谁，但是效率较低；最短时间优先的模型是将时间最短的订单优先处理，但是该模型对大订单不利，可能使得大订单长时间得到不解决。[2]文章提出一种按订单的优先级进行调度的模型。[3]在每次调度前，调度算法计算每个订单的优先级，并且每次都安排优先级最高的订单进行处理。
4订单优先级的定义
在基于优先级的订单调度模型中，订单需要交付的时间记为T1，订单提交时间为T2，订单中包含备件数量记为n，每个备件的准备时间为Ti（i=1，2，…，n），订单的价值记为V，订单预定义优先级为P1，当前时间记为T。 定义1：订单的紧迫系数a，订单越临近交付时间，其紧迫系数越高，计算公式为：
a=T1-T2ni-1Ti
定理1：当紧迫系数a大于0时，值越小，就越紧迫，优先级就越高。
证明：由紧迫系数的公式可得：
当a≤0时，订单的提交日期大于等于交付日期，订单过期。
当a<1时，订单的剩余时间小于订单的准备时间，时间紧迫，需要加班加点完成。
当a=1时，订单的剩余时间刚好等于订单的准备时间，可以按计划完成。
当a>1时，订单的剩余时间大于订单的准备时间，时间充裕。
定理1证明完毕。
定义2：订单的优先级我们记为Pn，定义订单的优先级计算公式为：
Pn=lg（V+ni=1TiT1-T）a×P1
由订单优先级的计算公式我们可以得知：
①当订单越紧迫时，订单的优先级越大。
②当订单的交付时间越临近，订单的优先级越大。
③当订单的备件准备时间越大，订单的优先级越大。
④当订单的备件价值越大时，订单的优先级越大。
⑤订单预定义的优先级越高，订单的优先级越大。
41基于优先级的出库订单调度算法
411备件库调度
用户提交出库订单，我们将订单记做Di，首先选择订单的服务备件库：
步骤1：订单调度算法首先检测订单对应的备件库是否满足订单的要求。
步骤2：若满足要求，将该订单发到其对应备件库的订单队列中，然后转向②部分。
步骤3：若不满足，订单调度算法扫描所有的备件库信息，并根据备件库选择原则选出最优备件库，然后将订单发到该备件库的订单队列中，然后转向②部分。
步骤4：若仍没有满足条件的备件庫，发出备件信息预警并生成采购订单。订单调度失败，通知订单人员，调度算法结束。
412订单出库的调度
在订单等待队列中的订单Di的优先级为Pi，其属性分别如定义1和定义2，基于优先级的订单调度算法表示如下：
步骤1：对订单等待队列中的所有订单Di，根据订单的实际情况对订单需要交付的时间、订单提交时间为T2、订单中包含备件数量、订单中每个备件的准备时间、订单的价值以及当前时间等属性进行赋值。
步骤2：对队列中所有的订单，通过定义1计算其紧迫系数a，若a<0，则表示订单已经过期，将其从订单队列中剔除。
步骤3：对队列中的所有订单，通过定义2计算其优先级Pn，选取优先级最大的订单进行处理（若订单的优先级相同，选择等待时间长进行处理），并从队列中剔除该订单。
步骤4：若队列中仍有订单等待，转向步骤2，否则，转向步骤5。
步骤5：订单全部完成，调度算法结束。
42实验验证
根据上述描述的订单备件库调度算法，我们在实验室环境下模拟了基于优先级的出库调度算法，并与先来先服务的调度算法进行比较，实验过程如下。
我们进行了3组订单数据的出库调度模拟，其中每组订单数包含5个订单信息，订单详细信息如下表所示。
5结论
无人值守的全自动备件库调度系统包括两部分：出入库调度和备件库调度。
出入库调度系统，根据库房的实际操作过程将整个过程分为入库订单调度和出库订单调度两部分，并根据各自的特点选择相应的调度算法。订单入库调度算法，选择了先来先服务的调度算法，保证所有的入库订单依次完成入库。订单出库的调度算法，对订单的优先级进行了定义，使用基于优先级的调度算法，保证优先级高的订单能够及时地响应，并且能够在很大程度上避免先来先服务和短订单优先的算法带来的弊端，保证订单调度算法具有较好的性能，对实际生产中的订单调度算法具有较好的参考价值。
备件库调度一般选择预定的备件库，当出现预定的备件库满足不了紧急需求时，选择一个代价最低的备件库。
参考文献：
[1]崔帅，楚蓝天，高凯作业调度算法[J].科技向导，2011（17）：110.
[2]张绕学，史美林计算机操作系统教程[M].2版北京：清华大学出版社，2004.
[3]刘洋，桂小林，徐玉文网格工作流中基于优先级的调度算法研究[J].西安交通大学学报，2006（4）.
[关键词]订单调度算法；先来先服务；基于优先级调度
[DOI]1013939/jcnkizgsc201801142
1研究背景
文章针对国家电网备件库的信息化目标——全自动无人值守备件库系统进行研究。无人值守的全自动备件库系统具备如下特点：①各级备件库库存减少到警戒线时能够预警并自动预测各备件的采购量并生成采购单，采购单确认后开始采购；②备件使用单位上报备件需求时，系统根据库存情况、备件需求的紧急情况确定出库单优先级，优先级高的优先满足；③对于库存可以满足的出库单（不需采购），综合考虑各使用单位分布情况和各级备件库的库存情况决定从哪个（或者哪些）备件库出库；④备件入库、出库不需人工干预。
文章研究的国家电网的备品备件库的订单调度算法，其订单特点为种类多、需求变动频繁、实时性强，在此背景下，同时具有很多订单的时候，计划与调度要具有敏捷性，能够解决订单的计划与调度的实时性，高效率地安排这些订单并满足订单需求。本文针对这一问题，首先对多订单的出入库调度进行研究，并提出相应的调度算法；其次，对于备件使用单位的备件需求，根据各级备件库的库存情况，设计调度算法，确定该需求从哪个（些）备件库下出库单。
2备件出入库调度系统
21问题描述
国家电网的库房中的备品、备件支撑整个企业的日常生产，如何保证库房中的备品备件有效地支撑企业的日常生产，成为一个亟待解决的问题。在日常的调度中，当库房中的备品、备件消耗后要及时补充相应物品，以保证生产的正常运行；当需要备品、备件的多个订单同时提交时，要及时响应订单，保证及时高效地完成所有订单需求。根据以上需求，我们将库房的订单调度模型抽象成两部分：订单入库和订单出库，通过相关的调度算法，及时响应各种订单信息。在同时需要进行入库和出库时，优先进行出库操作，当出库单都已经操作完成，或者现有库存已经不足以进行出库时，再进行入库操作。
22基于“先来先服务”的入库订单调度算法
在日常的库房维护中，库房管理员会根据备件库预警信息、日常的订单以及用户的反饋采购相应的备品、备件。当库房管理员采购来备品、备件准备放入库房，调度模型即生成一个入库的订单，并记录备品备件的名称、数量、价格、采购时间等相关的属性。该入库订单提交给库房调度系统，系统依据先来先服务的调度算法，根据订单的提交顺序依次处理，将备品、备件放在库房的相应位置，并做好记录，在系统数据库中更新相关信息。
3基于“先来先服务”的入库订单调度算法表示
步骤1：对采购的备品、备件生成相应的入库订单，并根据订单的实际情况对备品、备件的名称、数量、价格、采购时间的等相关属性进行赋值，然后将订单放入入库订单的等待队列中。
步骤2：对入库订单队列中所有的订单，库房调度系统根据其提交的时间顺序依次进行处理，处理完毕后将该订单从入库订单队列中提出，并在系统中更新相关的数据记录。
步骤3：若队列中仍有订单等待，转向步骤2，否则，转向步骤4。
步骤4：订单全部完成，调度算法结束。
31基于优先级的出库订单调度算法
当用户需要相应的备品、备件时，其会向库房调度系统提交一个出库订单，包含其所需要的备品、备件。库房调度系统会根据其相应的调度算法，及时响应订单，满足用户的需求。在日常的使用中，通常面临两个方面的问题：①备件库无法满足当前订单需求，如何快速有效地通过备件库调度来满足订单需求；②备件库面临提交的多个订单时，如何快速响应订单要求，满足订单需求。如何完善地解决上面两个问题，成为库房调度系统设计成败的关键。
基于优先级的出库订单调度算法主要包括两部分内容：备件库的选调度和出库订单的调度两部分。当用户提交出库订单后，库房调度系统首先根据订单的内容，首先判断对应备件库是否能满足订单需求，若不能满足通过备件库的调度能否满足订单需求。若满足需求后，备件库接收订单，根据出库订单调度算法进行订单的出库。
32备件库调度
国家电网备件库包括不同级别的多个备件库，并且分布在不同的区域。原则上，每个备件库都有其固定的服务范围（使用单位），在备件库的库存允许范围内，各个使用单位的备件需求都由相应的备件库提供。当备件订单需求十分急迫，但是对应的备件库因为备件不足难以提供时，采用优化算法，选择其他备件库，给该备件库生成出库单。选择算法如下：
①寻找那些可以满足本身服务任务基础上，能够额外满足该需求的备件库。
②选择一个代价（运费）最低的备件库。
33订单出库的调度算法
在库房调度系统的多订单调度问题中，最常见的调度模型为先来先服务和最短时间优先服务两种模型。[1]先来先服务调度模型实现最简单，谁先来先处理谁，但是效率较低；最短时间优先的模型是将时间最短的订单优先处理，但是该模型对大订单不利，可能使得大订单长时间得到不解决。[2]文章提出一种按订单的优先级进行调度的模型。[3]在每次调度前，调度算法计算每个订单的优先级，并且每次都安排优先级最高的订单进行处理。
4订单优先级的定义
在基于优先级的订单调度模型中，订单需要交付的时间记为T1，订单提交时间为T2，订单中包含备件数量记为n，每个备件的准备时间为Ti（i=1，2，…，n），订单的价值记为V，订单预定义优先级为P1，当前时间记为T。 定义1：订单的紧迫系数a，订单越临近交付时间，其紧迫系数越高，计算公式为：
a=T1-T2ni-1Ti
定理1：当紧迫系数a大于0时，值越小，就越紧迫，优先级就越高。
证明：由紧迫系数的公式可得：
当a≤0时，订单的提交日期大于等于交付日期，订单过期。
当a<1时，订单的剩余时间小于订单的准备时间，时间紧迫，需要加班加点完成。
当a=1时，订单的剩余时间刚好等于订单的准备时间，可以按计划完成。
当a>1时，订单的剩余时间大于订单的准备时间，时间充裕。
定理1证明完毕。
定义2：订单的优先级我们记为Pn，定义订单的优先级计算公式为：
Pn=lg（V+ni=1TiT1-T）a×P1
由订单优先级的计算公式我们可以得知：
①当订单越紧迫时，订单的优先级越大。
②当订单的交付时间越临近，订单的优先级越大。
③当订单的备件准备时间越大，订单的优先级越大。
④当订单的备件价值越大时，订单的优先级越大。
⑤订单预定义的优先级越高，订单的优先级越大。
41基于优先级的出库订单调度算法
411备件库调度
用户提交出库订单，我们将订单记做Di，首先选择订单的服务备件库：
步骤1：订单调度算法首先检测订单对应的备件库是否满足订单的要求。
步骤2：若满足要求，将该订单发到其对应备件库的订单队列中，然后转向②部分。
步骤3：若不满足，订单调度算法扫描所有的备件库信息，并根据备件库选择原则选出最优备件库，然后将订单发到该备件库的订单队列中，然后转向②部分。
步骤4：若仍没有满足条件的备件庫，发出备件信息预警并生成采购订单。订单调度失败，通知订单人员，调度算法结束。
412订单出库的调度
在订单等待队列中的订单Di的优先级为Pi，其属性分别如定义1和定义2，基于优先级的订单调度算法表示如下：
步骤1：对订单等待队列中的所有订单Di，根据订单的实际情况对订单需要交付的时间、订单提交时间为T2、订单中包含备件数量、订单中每个备件的准备时间、订单的价值以及当前时间等属性进行赋值。
步骤2：对队列中所有的订单，通过定义1计算其紧迫系数a，若a<0，则表示订单已经过期，将其从订单队列中剔除。
步骤3：对队列中的所有订单，通过定义2计算其优先级Pn，选取优先级最大的订单进行处理（若订单的优先级相同，选择等待时间长进行处理），并从队列中剔除该订单。
步骤4：若队列中仍有订单等待，转向步骤2，否则，转向步骤5。
步骤5：订单全部完成，调度算法结束。
42实验验证
根据上述描述的订单备件库调度算法，我们在实验室环境下模拟了基于优先级的出库调度算法，并与先来先服务的调度算法进行比较，实验过程如下。
我们进行了3组订单数据的出库调度模拟，其中每组订单数包含5个订单信息，订单详细信息如下表所示。
5结论
无人值守的全自动备件库调度系统包括两部分：出入库调度和备件库调度。
出入库调度系统，根据库房的实际操作过程将整个过程分为入库订单调度和出库订单调度两部分，并根据各自的特点选择相应的调度算法。订单入库调度算法，选择了先来先服务的调度算法，保证所有的入库订单依次完成入库。订单出库的调度算法，对订单的优先级进行了定义，使用基于优先级的调度算法，保证优先级高的订单能够及时地响应，并且能够在很大程度上避免先来先服务和短订单优先的算法带来的弊端，保证订单调度算法具有较好的性能，对实际生产中的订单调度算法具有较好的参考价值。
备件库调度一般选择预定的备件库，当出现预定的备件库满足不了紧急需求时，选择一个代价最低的备件库。
参考文献：
[1]崔帅，楚蓝天，高凯作业调度算法[J].科技向导，2011（17）：110.
[2]张绕学，史美林计算机操作系统教程[M].2版北京：清华大学出版社，2004.
[3]刘洋，桂小林，徐玉文网格工作流中基于优先级的调度算法研究[J].西安交通大学学报，2006（4）.