本发明涉及生产调度优化，具体地说是一种差异工件随机到达情况下单机批调度问题的求解方法
技术背景
随着实体经济和制造业的迅猛发展，企业间的竞争也愈发激烈，为了提升产品质量，降低生产成品，企业在生产制造时必须将有限的资源在有限的时间内创造出最大利润，因此，生产调度优化问题是现代化生产作业中的核心内容。批处理问题是一类具有很强应用背景的生产调度问题，它起源于半导体制造业，例如在半导体生产中的扩散工序阶段，芯片需要成批的放置在扩散炉中进行掺杂，以改变半导体的电学性质。同时，在氧化，老化测试等阶段都需要在批处理机中进行加工。批处理工序可同时加工多个工件且加工时间往往较长，例如芯片老化测试工序，其加工时间通常几倍甚至几十倍于其他工序，这类工序往往成为生产线中的瓶颈，因此提升该类工序的生产效率至关重要。此外，批调度问题还广泛存在于金属铸造，纺织品染整作业和港口货物装卸等领域。
传统批调度方法大多针对工件信息都预先可知的理想情况，但是在现实世界的制造系统中，生产调度系统的运行通常伴随着随机事件的发生。另外，在一些面向订单生产的企业中，未来的订单到达也是无法提前预知的随机事件。这些事件的发生可能导致原先制定的生产调度计划非最优甚至不可行。因此，在问题中考虑相关的随机因素，才能更真实的反应实际调度情况，目前针对随机批调度问题的研究也受到了广泛关注，但是现有的调度方法大多只考虑工件尺寸相同的情况，实际生产中不同种类的工件往往会有尺寸上的差异，此时分批决策会更加复杂，不仅在构建工件批时要考虑工件加工时间的差异，还要考虑工件尺寸的不同所可能造成的加工资源浪费。同时，现有处理随机批调度问题的方法只考虑了工件种类较少的情况，在工件种类增多的情况下，现有方法往往会遇到解空间急剧增加的问题，这极大的降低了算法的优化效果。
技术实现要素：
本发明专利是为了解决上述现有技术存在的不足之处，提出一种差异工件随机到达情况下单机批调度问题的求解方法，以期能对差异工件随机到达时的批处理机进行调度优化控制，减少系统代价，提高系统生产率，同时针对工件种类较多的情况下，解决解空间过大的问题，保持良好的优化效果。
本发明为解决技术问题采用如下技术方案：
一种差异工件随机到达情况下单机批调度问题的求解方法，其特点在于，按如下步骤进行：
步骤1、定义tk为系统第k个决策时刻，初始化决策时刻tk＝0,k＝0；
步骤2、提前计算出所有状态下9种启发式规则对应的批量加工方案，在删除多余相同方案后，将其作为各状态下的行动集；
步骤2.1、对当前缓冲库中所有工件按照加工时间由大到小进行排序；
步骤2.2、计算所有选择式启发式规则所对应的加工工件，作为对应规则的加工批；
步骤2.3、计算所有构建式启发式规则所对应的加工工件，作为对应规则的加工批；
步骤2.4、在某状态下若有多种启发式规则对应的加工批相同，则在该状态的行动集合中剔除多余相同的加工规则；
步骤3、利用强化学习中的q学习方法得到每个系统状态下的最优加工行动；
步骤3.1、初始化所有状态-行动对值，即q值表，设定总迭代次数为y，每次迭代学习步数为z，模拟退火温度ttemp和退火系数
步骤3.2、在第k个决策时刻，观察到的系统状态记为sk，此时系统采取的行动记为
步骤3.3、执行所选行动，观察系统环境反馈，即系统从当前决策时刻到下一决策时刻的转移信息
若系统采用某启发式规则加工工件，则代价由式(2)计算
上面式子中的三部分分别表示存储代价、流失代价和机器浪费代价，k1、k2和k3为各代价的权重，ai表示当前决策周期内第i类工件的加工个数，as为转移过程中到达并存储的工件个数，
步骤3.4、利用步骤3.3中计算好的状态转移信息对当前时刻的状态-行动对值
其中，
步骤3.5、令z＝z 1，k＝k 1，若z<z则转跳到步骤3.2；
步骤3.6、令y＝y 1，若y<y，则令z＝0，
步骤3.7、学习结束；
步骤4、利用学到的最优策略调度批处理机进行加工。
步骤1中所述系统为：
m类不同类型的工件缓存库和容量为c的批处理机所组成的系统中，记di,μi分别表示第i类工件的尺寸和加工率，满足容量约束的前提下，机器每次可加工由任意多个工件构成的一个加工批，机器的加工时间等于加工工件中所有加工时间的最大值；m类工件不断地随机到达当前系统并被存放在对应的缓存库中，每类缓存库的最大容量记为n，当工件到达系统时，如果该类工件的缓冲库已满，则该工件流失。系统的状态由各缓存库中存放的工件数目组成记为s＝(n1,n2,...,nm)，ni∈[0,n]；定义系统的决策时刻为批处理机加工完一批工件或批处理机空闲且有工件到达时。
步骤2中，利用启发式规则代替传统机器加工行动，本方法根据问题优化目标设计出若干启发式规则作为加工可选行动，这样既可加快算法收敛速度又能解决在工件品种较多情况下解空间过大的问题，行动集合记为d＝{h0,h1,h2,...,hb}，其中h0表示机器闲置不加工任何工件，b为启发式规则个数，定义系统在状态sa所采取的行动为
所述选择式启发式规则首先对缓冲库中的所有工件按加工时间由大到小进行排序后，采用bestfit规则进行工件分批，然后采用不同的选批规则从所有批中挑选一批工件进行加工，具体选批规则如下：
规则1spt-lr(shortestprocessingtime-largestprocessingrate)：最短加工时间-最大加工率规则
选择所有批中加工时间最短的批进行加工，若有多个批的加工时间相同，则选择其中加工率最大的批进行加工，加工率等于加工工件量除以加工时间。
规则2lcw-spt(leastcapacitywaste-shortestprocessingtime)：最小加工能力浪费-最短加工时间规则
选择所有批中机器加工能力浪费最小的批进行加工，若有多个批的机器加工能力浪费相同，则选择其中加工时间最短的批进行加工，机器加工能力浪费的度量公式为：1-机器利用率，其中机器利用率的计算公式为：加工工件量除以机器容量和加工时间的乘积。
规则3fb-lpr(fullestbuffer-largestprocessingrate)：缓存库存量最满-加工率最大规则
选择所有批中含有最满库存工件个数最多的批进行加工，若有多个批同时满足，则选择其中加工率最大的批进行加工。
规则4lq-spt(largestquantity-shortestprocessingtime)：最大工件量-最短加工时间规则
选择所有批中加工工件量最大的批进行加工，若有多个批同时满足，则选择其中加工时间最短的批进行加工。
所述构建式启发式规则的具体选批规则如下：
规则1fb-har(fullestbuffer-highestarrivalrate)：存量最满-最高到达率规则
步骤(1)、在满足批的容量约束的前提下，从当前存量最大的工件缓存库中尽可能多的选取工件放入批中，若有多种工件的存量均为最大，则选择到达率较高的，若到达率相同则选择尺寸较大的工件类型；
步骤(2)、计算批中剩余容量，在尺寸小于剩余容量的工件类型中选择存量最大的工件放入批中，重复该步骤直到没有工件可以放入批中为止。
规则2bf-cpt(fullestbuffer-closestprocessingtime)：存量最满-最相近加工时间规则
步骤(1)、在满足批的容量约束的前提下，从当前存量最大的工件缓存库中尽可能多的选取工件放入批中，若有多种工件的存量均为最大，则选择到达率较高的，若到达率相同则选择尺寸较大的工件类型；
步骤(2)、计算批中剩余容量，在尺寸小于剩余容量的工件类型中选择加工时间与当前批加工时间绝对值差最小的工件放入批中，若绝对值差相同，优先选择加工时间较小的工件，重复该步骤直到没有工件可以放入批中为止。
规则3lpt(longestprocessingtime)：最长加工时间规则
步骤(1)、在满足批的容量约束的前提下，尽可能多的选择加工时间最长的工件放入批中，若有多种工件的加工时间均为最长，则选择存量最多的，若存量相同则选择到达率较大的工件类型；
步骤(2)、计算批中剩余容量，在尺寸小于剩余容量的工件类型中选择加工时间最长的工件放入批中，重复该步骤直到没有工件可以放入批中为止。
规则4spt(shortestprocessingtime)：最短加工时间规则
步骤(1)、在满足批的容量约束的前提下，尽可能多的选择加工时间最短的工件放入批中，若有多种工件的加工时间均为最短，则选择存量最多的，若存量相同则选择到达率较大的工件类型；
步骤(2)、计算批中剩余容量，在尺寸小于剩余容量的工件类型中选择加工时间最短的工件放入批中，重复该步骤直到没有工件可以放入批中为止。
规则5lstr(largestsizetimerate)：最大尺寸时间比率规则
步骤(1)、在满足批的容量约束的前提下，尽可能多的选择工件尺寸除以时间比率最大的工件放入批中，若有多种工件的最大尺寸时间比率相同，则选择存量最多的，若存量相同则选择到达率较大的工件类型；
步骤(2)、计算批中剩余容量，在尺寸小于剩余容量的工件类型中选择工件尺寸除以时间比率最大的工件放入批中，重复该步骤直到没有工件可以放入批中为止。
与现有技术相比，本发明的有益效果在于：
1、本发明用于差异工件随机到达情况下单机批处理生产系统中，在工件随机到达的情况下，通过控制批处理机如何选择加工工件，达到提升加工系统加工率的目的。本发明以各缓存库中工件存量为系统状态，采用启发式规则和强化学习算法相结合的方式对该系统进行优化调度，有效地提升了系统加工率，减少了工件在该工序的平均逗留时间。
2、本发明在系统工件种类过多的情况下通过设计多个启发式规则作为系统行动来代替传统直接选取工件组合的行动。启发式规则易于实施，计算效率高，可根据系统特征设置，在某些特定的状态下有良好的求解效果，但由于系统的复杂性，无法简单得知每个启发式规则的适用范围，而强化学习方法具备全局搜索能力，能对每个特定的状态学到其最优行动，但在规模较大的问题中，由于任意满足机器容量限制的工件组合都可以作为行动，这种方式定义的可选行动会导致解空间急剧增加，这极大降低了算法的优化性能。因此，本发明将启发式规则和强化学习方法相结合，综合二者的优势，用全局优化能力较强的强化学习方法为每个状态选择合适的启发式规则，再用规则进行高效率的调度加工，这避免了在大规模问题下解空间激增的问题，同时，也提升了算法的搜索效率，提高了算法收敛速度。
3、本发明考虑了实际生产中的随机因素影响，由于上游生产系统的不确定性，可能无法提前准确知晓工件的到达时间，因此本发明在假设工件随机到达的情况下，给出了启发式规则和强化学习相结合的寻优方法，该强化学习方法不依赖于系统具体数学模型，只需根据实际工件到达情况和系统加工情况进行在线学习就可以有效地进行优化调度，该方法相比于以往方法更适应实际生产情况。
附图说明
附图用来提供对本发明的进一步理解，并且构成说明书的一部分，与本发明的实施例一起用于解释本发明，并不构成对本发明的限制。
图1为本发明方法流程图；
图2为本发明在生产系统的示意图；
图3为本发明方法在5品种工件算例下的代价优化曲线；
图4为本发明方法在5品种工件算例下的加工率优化曲线。
具体实施方式
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。
实施例1
本实施例中，一种考虑差异工件随机到达情况下单机批调度问题的求解方法，应用于如图2所示的m类工件由传送带随机传送到当前加工系统1、自动分拣装置2、m类缓冲库3、容量为c的批处理机4所构成的单机生产单元中；m类工件沿着传送带随机到达当前加工系统，由系统中的自动分拣装置2在捡取点将各工件放入到相对应的缓冲库3中，捡取时间忽略不计，若当前某缓冲库已满，则放弃捡取该类工件，该工件流失；每类缓存库只存放一类工件，每个缓存库容量记为n，假设第i个缓存库中存储的工件数量为ni，ni∈[0,n]，由m类缓存库中存储工件组成的系统状态为s＝(n1,n2,...,nm)，所有可能出现的状态构成系统的状态空间；容量为c的批处理机4表示该机器可以同时加工尺寸之和不超过c的多个工件，在满足容量约束的前提下，机器每次可加工由任意工件构成的批，机器的加工时间等于批中工件加工时间的最大值。
定义系统可选加工行动为各种启发式规则，d＝{h0,h1,h2,...,hb}表示行动集合，即启发式规则集合，其中h0表示机器闲置不加工任何工件，b为启发式规则个数，定义系统在状态sa所采取的行动为
选择式启发式规则从全局角度考虑，对当前缓冲库中所有工件进行分批，然后再从分好的批中基于目标准则选取待加工批，因此，该类启发式规则优先考虑所有工件分批的优劣，使每个批尽可能的高效利用机器加工能力，在此基础上再考虑调度目标。在进行分批时，首先对缓存库中所有工件进行排序，排序方法是按照工件加工时间由高到低对缓冲库中所有工件进行排序。排序完成后，对序列利用bestfit方法对工件进行分批，然后采用不同的选批规则从所有批中挑选一批工件进行加工。bestfit的具体实施方法为：选定序列中第一个工件，找到当前能容纳该工件且剩余容量最小的批，将该工件放入该批中，重复上述步骤直到对所有工件完成分批。各选择式启发式规则具体实施步骤如下：
规则1spt-lr(shortestprocessingtime-largestprocessingrate,最短加工时间-最大加工率)规则
选择所有批中加工时间最短的批进行加工，若有多个批的加工时间相同，则选择其中加工率最大的批进行加工(加工率等于加工工件量除以加工时间)。
规则2lcw-spt(leastcapacitywaste-shortestprocessingtime，最小加工能力浪费-最短加工时间)规则
选择所有批中机器加工能力浪费最小的批进行加工，若有多个批的机器加工能力浪费相同，则选择其中加工时间最短的批进行加工，加工能力浪费的度量为：1-机器利用率，其中机器利用率的计算公式为：加工工件量除以机器容量和加工时间的乘积。
规则3fb-lpr(fullestbuffer-largestprocessingrate，缓存库存量最满-加工率最大)规则
选择所有批中含有最满库存工件个数最多的批进行加工，若有多个批同时满足，则选择其中加工率最大的批进行加工。
规则4lq-spt(largestquantity-shortestprocessingtime，最大工件量-最短加工时间)规则
选择所有批中加工工件量最大的批进行加工，若有多个批同时满足，则选择其中加工时间最短的批进行加工。
构建式启发式规则优先考虑要优化的目标，在当前缓存库中选择最符合规则优化目标的工件构成工件批，在此基础上再考虑该加工批的机器利用率的情况，不考虑其他工件的分批构成和机器利用率情况。各构建式启发式规则具体实施步骤如下：
规则1fb-har(fullestbuffer-highestarrivalrate,存量最满-最高到达率)规则
步骤1、在满足批的容量约束的前提下，从当前存量最大的工件缓存库中尽可能多的选取工件放入批中，若有多种工件的存量均为最大，则选择到达率较高的，若到达率相同则选择尺寸较大的工件类型；
步骤2、计算批中剩余容量，在尺寸小于剩余容量的工件类型中选择存量最大的工件放入批中，重复该步骤直到没有工件可以放入批中为止。
规则2bf-cpt(fullestbuffer-closestprocessingtime，存量最满-最相近加工时间)规则
步骤1、在满足批的容量约束的前提下，从当前存量最大的工件缓存库中尽可能多的选取工件放入批中，若有多种工件的存量均为最大，则选择到达率较高的，若到达率相同则选择尺寸较大的工件类型；
步骤2、计算批中剩余容量，在尺寸小于剩余容量的工件类型中选择加工时间与当前批加工时间绝对值差最小的工件放入批中，若绝对值差相同，优先选择加工时间较小的工件，重复该步骤直到没有工件可以放入批中为止。
规则3lpt(longestprocessingtime，最长加工时间)规则
步骤1、在满足批的容量约束的前提下，尽可能多的选择加工时间最长的工件放入批中，若有多种工件的加工时间均为最长，则选择存量最多的，若存量相同则选择到达率较大的工件类型；
步骤2、计算批中剩余容量，在尺寸小于剩余容量的工件类型中选择加工时间最长的工件放入批中，重复该步骤直到没有工件可以放入批中为止。
规则4spt(shortestprocessingtime，最短加工时间)规则
步骤1、在满足批的容量约束的前提下，尽可能多的选择加工时间最短的工件放入批中，若有多种工件的加工时间均为最短，则选择存量最多的，若存量相同则选择到达率较大的工件类型；
步骤2、计算批中剩余容量，在尺寸小于剩余容量的工件类型中选择加工时间最短的工件放入批中，重复该步骤直到没有工件可以放入批中为止。
规则5lstr(largestsizetimerate，最大尺寸时间比率)规则
步骤1、在满足批的容量约束的前提下，尽可能多的选择工件尺寸除以时间比率最大的工件放入批中，若有多种工件的最大尺寸时间比率相同，则选择存量最多的，若存量相同则选择到达率较大的工件类型；
步骤2、计算批中剩余容量，在尺寸小于剩余容量的工件类型中选择工件尺寸除以时间比率最大的工件放入批中，重复该步骤直到没有工件可以放入批中为止。
定义系统的决策时刻为批处理机4加工完一批工件的时刻或批处理机4空闲且有工件到达的时刻；
根据上述系统特点和设计的各类启发式规则，所述差异工件随机到达情况下单机批调度问题的求解方法如图1所示，是按如下步骤进行：
步骤1、定义tk为系统第k个决策时刻，初始化决策时刻tk＝0,k＝0；
步骤2、提前计算出所有状态下9种启发式规则对应的批量加工方案，在删除多余相同方案后，将其作为各状态下的行动集；
步骤2.1、对当前缓冲库中所有工件按照加工时间由大到小进行排序；
步骤2.2、计算所有选择式启发式规则所对应的加工工件，作为对应规则的加工批；
步骤2.3、计算所有构建式启发式规则所对应的加工工件，作为对应规则的加工批；
步骤2.4、在某状态下若有多种启发式规则对应的加工批相同，则在该状态的行动集合中剔除多余相同的加工规则；
定义q值表中的元素为状态-行动对值，q值表的行表示系统状态，列表示系统行动，
步骤3、利用强化学习中的q学习方法得到每个系统状态下的最优加工行动；
步骤3.1、初始化所有状态-行动对值，即q值表，设定总迭代次数为y，每次迭代学习步数为z，模拟退火温度ttemp和退火系数
步骤3.2、在第k个决策时刻，观察到的系统状态记为sk，此时系统采取的行动记为
步骤3.3、执行所选行动，观察系统环境反馈，即系统从当前决策时刻到下一决策时刻的转移信息
若系统采用某启发式规则加工工件，则代价计算公式如下
由于工件间存在着尺寸差异，用一定时间内加工的工件个数来衡量批处理机的加工率显然是不合理的，为此使用工件量的概念对不同类型的工件进行统一度量，某工件的工件量计算公式为工件尺寸乘以工件加工时间。当系统处于长期稳定运行时，系统的到达工件量等于已加工的工件量和因缓冲库满而流失的工件量，所以提高系统加工率最关键的因素在于减少流失工件量。因此，系统的工件量流失是首要考虑的因素。另外从短期效益来看，减少当前决策周期内的机器浪费也能一定程度上提升加工率，同时少量的库存管理成本也是要考虑的因素。因此，根据上述分析，定义系统的三类代价：工件量存储代价、工件量流失代价和机器浪费代价。上面式子中的三部分分别表示存储代价、流失代价和机器浪费代价，k1、k2和k3为各代价的权重，可根据实际生产需求进行调整，ai表示当前决策周期内第i类工件的加工个数，as为转移过程中到达并存储的工件个数，
步骤3.4、利用步骤3.3中计算好的状态转移信息对当前时刻的状态-行动对值
其中，
步骤3.5、令z＝z 1，k＝k 1，若z<z则转跳到步骤3.2；
步骤3.6、令y＝y 1，若y<y，则令z＝0，
步骤3.7、学习结束；
步骤4、利用学到的最优策略调度批处理机进行加工
在上述步骤全部执行完成后，就可以根据学到的调度策略进行控制机器加工工件，即在任意一个系统状态下，选取最优启发式规则作为该系统状态的调度方法，机器根据该启发式规则调度工件进行加工。
本发明方法在5品种工件情况下对加工系统的代价和加工率优化效果分别如图3，图4所示，此例主要参数设置为：工件尺寸为(2，3，3，4，5)、批处理机容量为10，工件缓存库容量为5。可以看出本发明方法可以有效地对加工系统进行优化，提高加工率。此时系统共有7776个状态，若按照原始的工件排列组合作为系统待选行动的话，则有将近二十八万个状态-行动对值需要更新。这种情况下，解空间过于庞大，算法优化效率大幅下降，而且很难在有限的时间内探索到较好的解。在工件种类增多时，利用启发式规则作为行动则可以避免由工件排列组合数激增导致的解空间过于庞大的问题，在执行完步骤2后，此时系统的状态-行动对仅两万多个，这大大提高了算法效率，而且启发式规则是根据人为经验设计出的，每个规则在特定状态下都有较好的调度结果，强化学习算法只需要为每个状态选取最合适的规则即可，这样也大幅提升了算法的优化速度，使得算法快速收敛。
1.一种差异工件随机到达情况下单机批调度问题的求解方法，其特点在于，按如下步骤进行：
步骤1、定义tk为系统第k个决策时刻，初始化决策时刻tk＝0,k＝0；
步骤2、提前计算出所有状态下9种启发式规则对应的批量加工方案，在删除多余相同方案后，将其作为各状态下的行动集；
步骤2.1、对当前缓冲库中所有工件按照加工时间由大到小进行排序；
步骤2.2、计算所有选择式启发式规则所对应的加工工件，作为对应规则的加工批；
步骤2.3、计算所有构建式启发式规则所对应的加工工件，作为对应规则的加工批；
步骤2.4、在某状态下若有多种启发式规则对应的加工批相同，则在该状态的行动集合中剔除多余相同的加工规则；
步骤3、利用强化学习中的q学习方法得到每个系统状态下的最优加工行动；
步骤3.1、初始化所有状态-行动对值，即q值表，设定总迭代次数为y，每次迭代学习步数为z，模拟退火温度ttemp和退火系数
步骤3.2、在第k个决策时刻，观察到的系统状态记为sk，此时系统采取的行动记为
步骤3.3、执行所选行动，观察系统环境反馈，即系统从当前决策时刻到下一决策时刻的转移信息
若系统采用某启发式规则加工工件，则代价由式(2)计算
上面式子中的三部分分别表示存储代价、流失代价和机器浪费代价，k1、k2和k3为各代价的权重，ai表示当前决策周期内第i类工件的加工个数，as为转移过程中到达并存储的工件个数，
步骤3.4、利用步骤3.3中计算好的状态转移信息对当前时刻的状态-行动对值q(sk,vsk)进行更新，更新公式
其中，
步骤3.5、令z＝z 1，k＝k 1，若z<z则转跳到步骤3.2；
步骤3.6、令y＝y 1，若y<y，则令z＝0，
步骤3.7、学习结束；
步骤4、利用学到的最优策略调度批处理机进行加工。
2.根据权利要求1所述的一种差异工件随机到达情况下单机批调度问题的求解方法，其特点在于，步骤1中所述系统为：
由m类不同类型的工件缓存库和容量为c的批处理机所组成的系统，记di,μi分别表示第i类工件的尺寸和加工率，满足容量约束的前提下，机器每次可加工由任意多个工件构成的一个加工批，机器的加工时间等于加工工件中所有加工时间的最大值；m类工件不断地随机到达当前系统并被存放在对应的缓存库中，每类缓存库的最大容量记为n，当工件到达系统时，如果该类工件的缓冲库已满，则该工件流失；系统的状态由各缓存库中存放的工件数目组成记为s＝(n1,n2,...,nm)，ni∈[0,n]；定义系统的决策时刻为批处理机加工完一批工件或批处理机空闲且有工件到达时。
3.根据权利要求2所述的一种差异工件随机到达情况下单机批调度问题的求解方法，其特点在于，步骤2中所述行动集合用d＝{h0,h1,h2,...,hb}表示，其中h0表示机器闲置不加工任何工件，b为启发式规则个数，定义系统在状态sa所采取的行动为
4.根据权利要求3所述的一种差异工件随机到达情况下单机批调度问题的求解方法，其特点在于，步骤2中所述启发式规则分为两类：一类是对缓冲库中所有工件完全分批后，挑选特定批的选择式启发式规则；另一类是以基准工件构造成批的构建式启发式规则。
5.根据权利要求4所述的一种差异工件随机到达情况下单机批调度问题的求解方法，其特点在于，所述选择式启发式规则首先对缓冲库中的所有工件按加工时间由大到小进行排序后，采用bestfit规则进行工件分批，然后采用不同的选批规则从所有批中挑选一批工件进行加工，具体选批规则如下：
规则1spt-lr：最短加工时间-最大加工率规则
选择所有批中加工时间最短的批进行加工，若有多个批的加工时间相同，则选择其中加工率最大的批进行加工，加工率等于加工工件量除以加工时间；
规则2lcw-spt：最小加工能力浪费-最短加工时间规则
选择所有批中机器加工能力浪费最小的批进行加工，若有多个批的机器加工能力浪费相同，则选择其中加工时间最短的批进行加工，机器加工能力浪费的度量公式为：1-机器利用率，其中机器利用率的计算公式为：加工工件量除以机器容量和加工时间的乘积；
规则3fb-lpr：缓存库存量最满-加工率最大规则
选择所有批中含有最满库存工件个数最多的批进行加工，若有多个批同时满足，则选择其中加工率最大的批进行加工；
规则4lq-spt：最大工件量-最短加工时间规则
选择所有批中加工工件量最大的批进行加工，若有多个批同时满足，则选择其中加工时间最短的批进行加工。
6.根据权利要求4所述的一种差异工件随机到达情况下单机批调度问题的求解方法，其特点在于，所述构建式启发式规则的具体选批规则如下：
规则1fb-har：存量最满-最高到达率规则
步骤(1)、在满足批的容量约束的前提下，从当前存量最大的工件缓存库中尽可能多的选取工件放入批中，若有多种工件的存量均为最大，则选择到达率较高的，若到达率相同则选择尺寸较大的工件类型；
步骤(2)、计算批中剩余容量，在尺寸小于剩余容量的工件类型中选择存量最大的工件放入批中，重复该步骤直到没有工件可以放入批中为止；
规则2bf-cpt：存量最满-最相近加工时间规则
步骤(1)、在满足批的容量约束的前提下，从当前存量最大的工件缓存库中尽可能多的选取工件放入批中，若有多种工件的存量均为最大，则选择到达率较高的，若到达率相同则选择尺寸较大的工件类型；
步骤(2)、计算批中剩余容量，在尺寸小于剩余容量的工件类型中选择加工时间与当前批加工时间绝对值差最小的工件放入批中，若绝对值差相同，优先选择加工时间较小的工件，重复该步骤直到没有工件可以放入批中为止；
规则3lpt：最长加工时间规则
步骤(1)、在满足批的容量约束的前提下，尽可能多的选择加工时间最长的工件放入批中，若有多种工件的加工时间均为最长，则选择存量最多的，若存量相同则选择到达率较大的工件类型；
步骤(2)、计算批中剩余容量，在尺寸小于剩余容量的工件类型中选择加工时间最长的工件放入批中，重复该步骤直到没有工件可以放入批中为止；
规则4spt：最短加工时间规则
步骤(1)、在满足批的容量约束的前提下，尽可能多的选择加工时间最短的工件放入批中，若有多种工件的加工时间均为最短，则选择存量最多的，若存量相同则选择到达率较大的工件类型；
步骤(2)、计算批中剩余容量，在尺寸小于剩余容量的工件类型中选择加工时间最短的工件放入批中，重复该步骤直到没有工件可以放入批中为止；
规则5lstr：最大尺寸时间比率规则
步骤(1)、在满足批的容量约束的前提下，尽可能多的选择工件尺寸除以时间比率最大的工件放入批中，若有多种工件的最大尺寸时间比率相同，则选择存量最多的，若存量相同则选择到达率较大的工件类型；
步骤(2)、计算批中剩余容量，在尺寸小于剩余容量的工件类型中选择工件尺寸除以时间比率最大的工件放入批中，重复该步骤直到没有工件可以放入批中为止。
技术总结