基于工人转移场景下的赛汝系统调度方法及装置

1.本发明涉及赛汝系统调度技术领域，特别是涉及基于工人转移场景下的赛汝系统调度方法及装置。


背景技术：

2.随着经济全球化和新兴科技快速发展，制造业面临的商业环境发生重大变化，消费者需求结构逐渐多元化，个性化，产品生命周期短，技术更新迭代快，呈现多品种，小批量的特征。如何在c2b的商业模式下快速响应客户需求，是企业提升竞争力的关键。在此背景下，起源于日本电子装配企业的赛汝生产系统(seru production system,sps)可以通过工人灵活重组提升生产系统柔性，快速满足消费者个性化需求。sps包含多个生产单元(称为赛汝)，每个赛汝内部包含一名或者多名工人，简单易移动设备和工作台。因此，sps中装配单元可以根据顾客需求变化构建，拆解和调整。可以在生产过程中通过灵活调整单元内的工人，优化产品加工能力，提升系统对需求变化的响应能力。研究表明，sps不仅可以为企业带来经济效益，还可以提高工人的自主性和积极性，减少工人数量，减少库存，降低物料消耗和能源排放。由于其优势，sps已成功应用于多家企业，如索尼，佳能，松下，nec和富士康等。但是，sps发挥其高柔性优势的背后需要调度优化算法的支撑，来保证sps实施的可行性和高效性。因此，为sps设计高效的调度方法，能够更好的发挥sps的柔性优势，提高生产效率，快速满足消费者个性化需求，助力企业提升核心竞争力。
3.考虑工人转移场景下的赛汝系统调度问题(seru system scheduling problem with worker transfer,sssp-wt)涉及四个耦合子问题：工人-批次分配，工人-任务分配，批次-赛汝分配，和批次排序。作为一个复杂的组合优化问题，其生产调度过程具有高度的耦合性、非线性、多极小、强约束、np-hard、多目标等特点，对于优化求解的挑战很大。现有的调度优化算法主要包括三大类：精确算法，启发式算法和智能优化算法。其中，精确算法包括分支定界，分支定价，线性规划等，虽然可以得到全局最优解，但随着问题规模的增加，该类算法耗费的计算量巨大，无法实现问题的高效求解；启发式算法利用设定好的启发式规则对解空间进行搜索，可以保证求解效率，但无法保证解的质量；智能优化算法可以通过迭代搜索，得到问题的较优解，但传统的智能优化大多遵循种群初始化，交叉变异，个体选择等基本步骤，该类方法存在问题特征结合不够和收敛速度慢的缺陷。


技术实现要素：

4.本发明旨在至少在一定程度上解决相关技术中的技术问题之一。
5.为此，本发明提出基于工人转移场景下的赛汝系统调度方法，算法耗费的计算量小，可实现问题的高效求解并保证求解效率和求解的质量，实现高效智能的调度。
6.本发明的另一个目的在于提出一种基于工人转移场景下的赛汝系统调度装置。
7.为达上述目的，本发明一方面提出一种基于工人转移场景下的赛汝系统调度方法，包括：
8.获取赛汝系统调度问题的耦合子问题，并基于预设的编解码规则得到第一多个个体构建用于优化所述耦合子问题的第一种群和第二种群；
9.对所述第一种群进行基于概率学习的搜索以及对第二种群进行迭代贪婪搜索，并基于第一搜索结果和q learning的选择机制选择要进入的种群；
10.对所述选择要进入的种群中第二多个个体进行基于q learning的局部搜索得到第二搜索结果；
11.基于所述第二搜索结果并利用所述第二多个个体更新概率模型；
12.判断更新后的概率模型是否满足终止准则，若满足，则输出结果。
13.另外，根据本发明上述实施例的基于工人转移场景下的赛汝系统调度方法还可以具有以下附加的技术特征：
14.进一步地，在本发明的一个实施例中，所述终止准则为cpu运行时间；所述耦合子问题，包括工人-批次分配、工人-任务分配、批次-赛汝分配和批次排序；所述编解码规则，包括四列编码结构和解码规则；其中，
15.所述四列编码结构，包括第一列表示批次的加工顺序；第二列表示批次所在赛汝；第三列表示每个批次的加工工人；第四列表示批次内部的任务分配序列；
16.所述解码规则，包括根据四列编码结构，逐行将批次输入赛汝系统的最早加工位置，在确定批次的开始加工时间时考虑工人的占用情况，在每个批次内部，按照任务分配序列依次分给最早可用工人，如果存在多个可用工人则随机选择工人加工。
17.进一步地，在本发明的一个实施例中，所述对所述第一种群进行基于概率学习的搜索以及对第二种群进行迭代贪婪搜索，包括：
18.对所述第一种群进行基于概率模型的搜索方法优化所述工人-批次分配，包括：建立一个b行w列的概率矩阵p，用于描述候选解在搜索空间的分布信息，其中，p中每个元素p
b,w
(b＝1，
…
，b；w＝1，
…
，w)表示工人w加工批次b的概率，对于批次b，遍历p中第b行的w个元素，工人w加工批次b的概率为p
b,w
，不加工批次的概率为1-p
b,w
，依次选择工人是否加工批次b，最终确定每个批次参与加工的工人。
19.进一步地，在本发明的一个实施例中，所述对所述第一种群进行基于概率学习的搜索以及对第二种群进行迭代贪婪搜索，还包括：
20.对所述第二种群进行基于迭代贪婪搜索优化批次分配和批次排序，包括：每次迭代，对批次分配序列ω和批次排序序列执行如下操作：解构、重构和局部搜索；其中，
21.在解构阶段，在中随机选择一个位置，将当前位置之后的批次全部取出；
22.在重构阶段，将取出的每一个批次，放入到使总拖期最小的位置上，重复以上操作直到所有批次全部放回；
23.在局部搜索阶段，依次执行预设的四种邻域搜索操作，如果某个操作改进目标值，则基于新解重新遍历搜索；否则，则执行下一种操作，直到所有操作都进行完毕。
24.进一步地，在本发明的一个实施例中，通过所述基于q learning的局部搜索优化所述工人-任务分配，其中，对每一个批次b执行如下步骤：
25.步骤1：令d＝1；count＝0；
26.步骤2：从任务分配序列v中随机选择d个连续的任务序列并从v中移除；
27.步骤3：将插入到v中所有可行位置，形成新的任务序列v
′
，如果目标值tt(v
′
)＜
tt(v)，则用v
′
替代v，同时令count＝count+1；
28.步骤4：如果count＞0，则令d＝1；否则，d＝d+1；
29.步骤5：判断是否满足条件d≤d
max
，如果满足则转至步骤2，否则停止迭代；其中，d
max
表示局部搜索的深度。
30.为达上述目的，本发明另一方面提出一种基于工人转移场景下的赛汝系统调度装置，包括：
31.种群初始化模块，用于获取赛汝系统调度问题的耦合子问题，并基于预设的编解码规则得到第一多个个体构建用于优化所述耦合子问题的第一种群和第二种群；
32.双种群协同搜索模块，用于对所述第一种群进行基于概率学习的搜索以及对第二种群进行迭代贪婪搜索，并基于第一搜索结果和q learning的选择机制选择要进入的种群；
33.局部搜索模块，用于对所述选择要进入的种群中第二多个个体进行基于qlearning的局部搜索得到第二搜索结果；
34.概率模型更新模块，用于基于所述第二搜索结果并利用所述第二多个个体更新概率模型；
35.终止准则判断模块，用于判断更新后的概率模型是否满足终止准则，若满足，则输出结果。
36.本发明实施例的基于工人转移场景下的赛汝系统调度方法和装置，耗费的计算量小，不仅可实现问题的高效求解并保证求解效率和求解的质量，还能实现高效智能的调度。
37.本发明附加的方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。
附图说明
38.本发明上述的和/或附加的方面和优点从下面结合附图对实施例的描述中将变得明显和容易理解，其中：
39.图1是根据本发明实施例的基于工人转移场景下的赛汝系统调度方法的流程图；
40.图2是根据本发明实施例的五个工人和四个批次的编解码实例示意图；
41.图3是根据本发明实施例的基于工人转移场景下的赛汝系统调度装置的结构示意图。
具体实施方式
42.需要说明的是，在不冲突的情况下，本发明中的实施例及实施例中的特征可以相互组合。下面将参考附图并结合实施例来详细说明本发明。
43.为了使本技术领域的人员更好地理解本发明方案，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分的实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都应当属于本发明保护的范围。
44.下面参照附图描述根据本发明实施例提出的基于工人转移场景下的赛汝系统调
度方法和装置。
45.图1是本发明实施例的基于工人转移场景下的赛汝系统调度方法的流程图。
46.如图1所示，该方法包括但不限于以下步骤：
47.s1，获取赛汝系统调度问题的耦合子问题，并基于预设的编解码规则得到第一多个个体构建用于优化所述耦合子问题的第一种群和第二种群；
48.s2，对第一种群进行基于概率学习的搜索以及对第二种群进行迭代贪婪搜索，并基于第一搜索结果和q learning的选择机制选择要进入的种群；
49.s3，对所述选择要进入的种群中第二多个个体进行基于q learning的局部搜索得到第二搜索结果；
50.s4，基于所述第二搜索结果并利用所述第二多个个体更新概率模型；
51.s5，判断更新后的概率模型是否满足终止准则，若满足，则输出结果。
52.可以理解的是，本发明考虑的sssp-wt描述如下：w个技能水平不同的工人加工b个不同类型的批次。每个批次包含qb个同一类型的产品，每种类型的产品需要的加工任务不同。工人为多技能工，即他们可以处理一个或多个任务。该问题可以分解为四个耦合子问题：1)工人-批次分配：确定每个批次的加工工人；2)工人-任务分配：确定批次中每个工人的加工任务；3)批次-赛汝分配：确定各个赛汝中分配的批次；4)批次排序：确定每个赛汝中批次的加工顺序；问题假设如下：产品分批处理，且批次不可拆分；已知每个批次的需求，类型和标准处理时间；允许工人在各个赛汝间转移，且移动时间忽略不计；一个任务只能由一个工人负责，每个工人可以负责多项任务。目标为所有批次的总拖期最小。
53.具体地，针对问题描述，本发明的基于工人转移场景下的赛汝系统调度方法的步骤可以包括：
54.步骤s1：种群初始化，产生ps个个体；
55.步骤s2：建立两个种群分别用于优化不同子问题，对种群1执行基于概率学习的搜索，对种群2执行迭代贪婪搜索，设计基于q learning的选择机制对种群进行选择；
56.步骤s3：选取种群中en＝η*ps个精英个体，执行基于q learning的局部搜索；
57.步骤s4：利用精英个体更新概率模型；
58.步骤s5：判断是否满足终止准则，若满足则输出结果；否则转至步骤2。
59.其中，终止准则为cpu运行时间：β
×w×
b。
60.进一步地，对编解码规则以及各个环节的设计进行详细阐述：
61.在一个实施例中，sssp-wt需要考虑四个耦合的子问题：工人-批次分配、工人-任务分配、批次-赛汝分配和批次排序。设计一种四列编码结构表征一个完整解：第一列表示批次的加工顺序；第二列表示批次所在赛汝；第三列表示每个批次的加工工人；第四列表示批次内部的任务分配序列。解码规则为：首先，根据编码结构，逐行将批次放入赛汝系统的最早加工位置，同时，在确定批次的开始加工时间时考虑工人的占用情况。然后，在每个批次内部，按照任务分配序列依次分给最早可用工人，如果存在多个可用工人则随机选择工人加工。图2是一个5个工人和4个批次的编解码实例。按照如上编码规则，随机产生ps个个体构成初始种群。
62.在一个实施例中，双种群协同搜索，包括基于概率学习的搜索和迭代贪婪搜索以及基于q learning的选择机制。
63.基于概率学习的搜索：针对种群1，设计一种基于概率模型的搜索方法优化工人-批次分配。建立一个b行w列的概率矩阵p，用于描述候选解在搜索空间的分布信息。其中，p中每个元素p
b,w
(b＝1，...，b；w＝1，...，w)表示工人w加工批次b的概率。对于批次b，遍历p中第b行的w个元素，工人w加工批次b的概率为p
b,w
，不加工批次的概率为1-p
b,w
，依次选择工人是否加工批次b，最终确定每个批次参与加工的工人。
64.迭代贪婪搜索：针对种群2，设计迭代贪婪搜索优化批次分配和排序。每次迭代，对批次分配序列ω和批次排序序列执行如下操作：解构，重构和局部搜索。在解构阶段，在中随机选择一个位置，将该位置之后的批次全部取出；在重构阶段，将取出的每一个批次，放入到使总拖期最小的位置上，重复以上操作直到所有批次全部放回；在局部搜索阶段，依次执行以下四种邻域搜索操作，如果某个操作改进了目标值，则基于新解重新遍历搜索；否则，则执行下一种操作，直到所有操作都进行完毕：
65.操作1：从中随机选择2个批次，交换它们的位置；
66.操作2：从中随机选择1个批次，将其插入中任意位置；
67.操作3：从中随机选择2个批次位置，将其间所有批次逆序；
68.操作4：在ω中随机选择1个位置，改变其批次所在的赛汝编号；
69.基于q learning的选择机制：强化学习(reinforcement learning，rl)技术通过智能体与环境的不断交互，在试错过程中学习决策策略，使执行的动作实现累计收益最大化。可以利用rl技术挖掘搜索过程中产生的知识并指导搜索行为，提高搜索效率。本发明融合rl中的q learning算法，设计了基于q learning的选择机制用于指导个体在每一代中选择要进入的种群，具体设计细节如下：
70.状态：提炼不同问题的特征作为其状态。使用所有批次处理时间标准化后的均值描述工人-批次分配问题，如公式(1)所示；采用产生拖期的批次数占批次总数的比例来描述批次分配和排序问题的状态，如公式(2)所示。
[0071][0072]
s2＝n
tardiness
/b
ꢀꢀꢀꢀ
(2)
[0073]
其中pt
min
和pt
max
分别表示所有批次中最小和最大批次处理时间，ptb表示批次b的处理时间，n
tardiness
表示所有产生拖期的批次总数。将二维连续状态(s1，s2)映射为一个离散状态首先，将两个[0.1]区间离散为f个均匀分布的子区间，然后，分别确定s1和s2属于的两个子区间f1和f2，例如：s1∈[(f
1-1)/f，f1/f]，f1∈{1，2，...，f}。最终确定映射的离散状态vf，其中f＝(f
1-1)*f+f2。
[0074]
动作：在每一代，智能体感知当前状态然后执行相应动作。在该机制中两个动作定义为：1)进入种群1；2)进入种群2。
[0075]
奖励：智能体通过执行合适的动作实现累计收益最大化，因此合适的奖励设计有助于智能体的高效学习。rl-cca中，将目标函数的改善程度定义为奖励，如等式(3)所示。
[0076]
reward＝max(tt
(g-1)-tt
(g)
/tt
(g-1)
，0)
ꢀꢀꢀꢀ
(3)
[0077]
其中，tt
(g)
为第g代的批次总拖期，如果没有改善，则奖励为0。
[0078]
在一个实施例中，基于q learning的局部搜索，为了增强算法的局部探索能力，设计基于q learning的局部搜索操作优化工人-任务分配，其中，对每一个批次b执行如下步骤：
[0079]
步骤1：令d＝1；count＝0；
[0080]
步骤2：从任务分配序列v中随机选择d个连续的任务序列并将其从v中移除；
[0081]
步骤3：将插入到v中所有可行位置，形成新的任务序列v
′
，如果目标值tt(v
′
)＜tt(v)，则用v
′
替代v，同时令count＝count+1；
[0082]
步骤4：如果count＞0，则令d＝1；否则，d＝d+1；
[0083]
步骤5：判断是否满足条件d≤d
max
，如果满足则转至步骤2，否则停止迭代；其中d
max
表示局部搜索的深度。
[0084]
使用q learning技术在搜索过程中不断调整d
max
，进而调整算法在不同阶段局部搜索的程度，有利于提高算法的搜索效率。具体设计细节如下：状态定义为：1)s＝1，表示局部搜索操作对目标函数有改进，2)s＝0，表示局部搜索操作对目标函数没有改进；动作定义为：d
max
＝1，d
max
＝2，d
max
＝3；奖励定义如等式(3)所示。
[0085]
在一个实施例中，更新概率模型，为了使概率模型能表征优势群体的分布，每次迭代选择en个精英解用于更新概率模型，更新公式如下：
[0086][0087][0088]
其中λ为学习率，为精英解的示性函数。
[0089]
根据本发明实施例的基于工人转移场景下的赛汝系统调度方法，可以法实现问题的高效求解，得到问题最优解并实现智能高效调度，还能够更好的发挥sps的柔性优势，提高生产效率，快速满足消费者个性化需求，助力企业提升核心竞争力。
[0090]
为了实现上述实施例，如图3所示，本实施例中还提供了基于工人转移场景下的赛汝系统调度装置10，该装置10包括，种群初始化模块100、双种群协同搜索模块200、局部搜索模块300、概率模型更新模块400和终止准则判断模块500。
[0091]
种群初始化模块100，用于获取赛汝系统调度问题的耦合子问题，并基于预设的编解码规则得到第一多个个体构建用于优化耦合子问题的第一种群和第二种群；
[0092]
双种群协同搜索模块200，用于对第一种群进行基于概率学习的搜索以及对第二种群进行迭代贪婪搜索，并基于第一搜索结果和q learning的选择机制选择要进入的种群；
[0093]
局部搜索模块300，用于对选择要进入的种群中第二多个个体进行基于qlearning的局部搜索得到第二搜索结果；
[0094]
概率模型更新模块400，用于基于第二搜索结果并利用所述第二多个个体更新概率模型；
[0095]
终止准则判断模块500，用于判断更新后的概率模型是否满足终止准则，若满足，则输出结果。
[0096]
进一步地，终止准则为cpu运行时间；耦合子问题，包括工人-批次分配、工人-任务分配、批次-赛汝分配和批次排序；所述编解码规则，包括四列编码结构和解码规则；其中，
[0097]
所述四列编码结构，包括第一列表示批次的加工顺序；第二列表示批次所在赛汝；第三列表示每个批次的加工工人；第四列表示批次内部的任务分配序列；
[0098]
所述解码规则，包括根据四列编码结构，逐行将批次输入赛汝系统的最早加工位置，在确定批次的开始加工时间时考虑工人的占用情况，在每个批次内部，按照任务分配序列依次分给最早可用工人，如果存在多个可用工人则随机选择工人加工。
[0099]
进一步地，上述双种群协同搜索模块200，还用于：
[0100]
对第一种群进行基于概率模型的搜索方法优化工人-批次分配，包括：建立一个b行w列的概率矩阵p，用于描述候选解在搜索空间的分布信息，其中，p中每个元素p
b,w
(b＝1，
…
，b；w＝1，
…
，w)表示工人w加工批次b的概率，对于批次b，遍历p中第b行的w个元素，工人w加工批次b的概率为p
b,w
，不加工批次的概率为1-p
b,w
，依次选择工人是否加工批次b，最终确定每个批次参与加工的工人。
[0101]
进一步地，上述双种群协同搜索模块200，还用于：
[0102]
对所述第二种群进行基于迭代贪婪搜索优化批次分配和批次排序，包括：每次迭代，对批次分配序列ω和批次排序序列执行如下操作：解构、重构和局部搜索；其中，
[0103]
在解构阶段，在中随机选择一个位置，将当前位置之后的批次全部取出；
[0104]
在重构阶段，将取出的每一个批次，放入到使总拖期最小的位置上，重复以上操作直到所有批次全部放回；
[0105]
在局部搜索阶段，依次执行预设的四种邻域搜索操作，如果某个操作改进目标值，则基于新解重新遍历搜索；否则，则执行下一种操作，直到所有操作都进行完毕。
[0106]
进一步地，上述局部搜索模块300，还用于通过所述基于q learning的局部搜索作优化所述工人-任务分配，其中，对每一个批次b执行如下子模块：
[0107]
第一子模块，用于令d＝1；count＝0；
[0108]
第二子模块，用于从任务分配序列v中随机选择d个连续的任务序列并从v中移除；
[0109]
第三子模块，用于将插入到v中所有可行位置，形成新的任务序列v
′
，如果目标值tt(v
′
)＜tt(v)，则用v
′
替代v，同时令count＝count+1；
[0110]
第四子模块，用于如果count＞0，则令d＝1；否则，d＝d+1；
[0111]
第五子模块，用于判断是否满足条件d≤d
max
，如果满足则转至第二子模块否则停止迭代；其中，d
max
表示局部搜索的深度。
[0112]
根据本发明实施例的基于工人转移场景下的赛汝系统调度装置，可以法实现问题的高效求解，得到问题最优解并实现智能高效调度，还能够更好的发挥sps的柔性优势，提高生产效率，快速满足消费者个性化需求，助力企业提升核心竞争力。
[0113]
在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结合和组合。
[0114]
此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者
隐含地包括至少一个该特征。在本发明的描述中，“多个”的含义是至少两个，例如两个，三个等，除非另有明确具体的限定。

技术特征：
1.一种基于工人转移场景下的赛汝系统调度方法，其特征在于，包括以下步骤：获取赛汝系统调度问题的耦合子问题，并基于预设的编解码规则得到第一多个个体构建用于优化所述耦合子问题的第一种群和第二种群；对所述第一种群进行基于概率学习的搜索以及对第二种群进行迭代贪婪搜索，并基于第一搜索结果和q learning的选择机制选择要进入的种群；对所述选择要进入的种群中第二多个个体进行基于q learning的局部搜索得到第二搜索结果；基于所述第二搜索结果并利用所述第二多个个体更新概率模型；判断更新后的概率模型是否满足终止准则，若满足，则输出结果。2.根据权利要求1所述的方法，其特征在于，所述终止准则为cpu运行时间；所述耦合子问题，包括工人-批次分配、工人-任务分配、批次-赛汝分配和批次排序；所述编解码规则，包括四列编码结构和解码规则；其中，所述四列编码结构，包括第一列表示批次的加工顺序；第二列表示批次所在赛汝；第三列表示每个批次的加工工人；第四列表示批次内部的任务分配序列；所述解码规则，包括根据四列编码结构，逐行将批次输入赛汝系统的最早加工位置，在确定批次的开始加工时间时考虑工人的占用情况，在每个批次内部，按照任务分配序列依次分给最早可用工人，如果存在多个可用工人则随机选择工人加工。3.根据权利要求2所述的方法，其特征在于，所述对所述第一种群进行基于概率学习的搜索以及对第二种群进行迭代贪婪搜索，包括：对所述第一种群进行基于概率模型的搜索方法优化所述工人-批次分配，包括：建立一个b行w列的概率矩阵p，用于描述候选解在搜索空间的分布信息，其中，p中每个元素p
b,w
(b＝1,
…
,b；w＝1,
…
,w)表示工人w加工批次b的概率，对于批次b，遍历p中第b行的w个元素，工人w加工批次b的概率为p
b,w
，不加工批次的概率为1-p
b,w
，依次选择工人是否加工批次b，最终确定每个批次参与加工的工人。4.根据权利要求3所述的方法，其特征在于，所述对所述第一种群进行基于概率学习的搜索以及对第二种群进行迭代贪婪搜索，还包括：对所述第二种群进行基于迭代贪婪搜索优化批次分配和批次排序，包括：每次迭代，对批次分配序列ω和批次排序序列执行如下操作：解构、重构和局部搜索；其中，在解构阶段，在中随机选择一个位置，将当前位置之后的批次全部取出；在重构阶段，将取出的每一个批次，放入到使总拖期最小的位置上，重复以上操作直到所有批次全部放回；在局部搜索阶段，依次执行预设的四种邻域搜索操作，如果某个操作改进目标值，则基于新解重新遍历搜索；否则，则执行下一种操作，直到所有操作都进行完毕。5.根据权利要求2所述的方法，其特征在于，通过所述基于q learning的局部搜索优化所述工人-任务分配，其中，对每一个批次b执行如下步骤：步骤1：令d＝1；count＝0；步骤2：从任务分配序列v中随机选择d个连续的任务序列并从υ中移除；步骤3：将插入到υ中所有可行位置，形成新的任务序列v
′
，如果目标值tt(υ
′
)<t(v)，则用v
′
替代υ，同时令count＝count+1；
步骤4：如果count>0，则令d＝1；否则，d＝d+1；步骤5：判断是否满足条件d≤d
max
，如果满足则转至步骤2，否则停止迭代；其中，d
max
表示局部搜索的深度。6.一种基于工人转移场景下的赛汝系统调度装置，其特征在于，包括：种群初始化模块，用于获取赛汝系统调度问题的耦合子问题，并基于预设的编解码规则得到第一多个个体构建用于优化所述耦合子问题的第一种群和第二种群；双种群协同搜索模块，用于对所述第一种群进行基于概率学习的搜索以及对第二种群进行迭代贪婪搜索，并基于第一搜索结果和q learning的选择机制选择要进入的种群；局部搜索模块，用于对所述选择要进入的种群中第二多个个体进行基于qlearning的局部搜索得到第二搜索结果；概率模型更新模块，用于基于所述第二搜索结果并利用所述第二多个个体更新概率模型；终止准则判断模块，用于判断更新后的概率模型是否满足终止准则，若满足，则输出结果。7.根据权利要求6所述的装置，其特征在于，所述终止准则为cpu运行时间；所述耦合子问题，包括工人-批次分配、工人-任务分配、批次-赛汝分配和批次排序；所述编解码规则，包括四列编码结构和解码规则；其中，所述四列编码结构，包括第一列表示批次的加工顺序；第二列表示批次所在赛汝；第三列表示每个批次的加工工人；第四列表示批次内部的任务分配序列；所述解码规则，包括根据四列编码结构，逐行将批次输入赛汝系统的最早加工位置，在确定批次的开始加工时间时考虑工人的占用情况，在每个批次内部，按照任务分配序列依次分给最早可用工人，如果存在多个可用工人则随机选择工人加工。8.根据权利要求7所述的装置，其特征在于，所述双种群协同搜索模块，还用于：对所述第一种群进行基于概率模型的搜索方法优化所述工人-批次分配，包括：建立一个b行w列的概率矩阵p，用于描述候选解在搜索空间的分布信息，其中，p中每个元素p
b,w
(b＝1,
…
,b；w＝1,
…
,w)表示工人w加工批次b的概率，对于批次b，遍历p中第b行的w个元素，工人w加工批次b的概率为p
b,w
，不加工批次的概率为1-p
b,w
，依次选择工人是否加工批次d，最终确定每个批次参与加工的工人。9.根据权利要求8所述的装置，其特征在于，所述双种群协同搜索模块，还用于：对所述第二种群进行基于迭代贪婪搜索优化批次分配和批次排序，包括：每次迭代，对批次分配序列ω和批次排序序列执行如下操作：解构、重构和局部搜索；其中，在解构阶段，在中随机选择一个位置，将当前位置之后的批次全部取出；在重构阶段，将取出的每一个批次，放入到使总拖期最小的位置上，重复以上操作直到所有批次全部放回；在局部搜索阶段，依次执行预设的四种邻域搜索操作，如果某个操作改进目标值，则基于新解重新遍历搜索；否则，则执行下一种操作，直到所有操作都进行完毕。10.根据权利要求7所述的装置，其特征在于，所述局部搜索模块，还用于通过所述基于q learning的局部搜索作优化所述工人-任务分配，其中，对每一个批次b执行如下子模块：第一子模块，用于令d＝1；count＝0；
第二子模块，用于从任务分配序列υ中随机选择d个连续的任务序列并从v中移除；第三子模块，用于将插入到v中所有可行位置，形成新的任务序列v
′
，如果目标值tt(v
′
)<t(υ)，则用υ
′
替代v，同时令count＝count+1；第四子模块，用于如果count>0，则令d＝1；否则，d＝d+1；第五子模块，用于判断是否满足条件d≤d
max
，如果满足则转至第二子模块否则停止迭代；其中，d
max
表示局部搜索的深度。

技术总结
本发明公开了基于工人转移场景下的赛汝系统调度方法及装置，该方法包括：获取赛汝系统调度问题的耦合子问题，并基于预设的编解码规则得到第一多个个体构建用于优化耦合子问题的第一种群和第二种群；对第一种群进行基于概率学习的搜索以及对第二种群进行迭代贪婪搜索，并基于第一搜索结果和Q learning的选择机制选择要进入的种群；对选择要进入的种群中第二多个个体进行基于Q learning的局部搜索得到第二搜索结果；基于第二搜索结果并利用第二多个个体更新概率模型；判断更新后的概率模型是否满足终止准则，若满足，则输出结果。本发明能够实现高效的智能调度。明能够实现高效的智能调度。明能够实现高效的智能调度。


技术研发人员：王凌 吴玉婷
受保护的技术使用者：清华大学
技术研发日：2023.06.08
技术公布日：2023/9/23