一种基于下界最小化的柔性作业车间调度方法

本发明属于工业智能制造领域，具体涉及一种基于下界最小化的柔性作业车间调度方法。

背景技术：

1、在典型的智能制造场景中，产品由多个加工步骤组成，每个加工步骤都可以由多台机器或人员执行。加工顺序的安排、时间安排等因素直接影响生产效率和交货时间。柔性作业车间调度问题对工厂的生产过程进行建模，分析制造资源的配置与优化，对提高生产效率，降低生产成本具有重要作用。

2、由于柔性作业车间调度问题是np困难的组合优化问题，随着作业、任务和机器数量的增加，可能的调度组合呈指数级增长，从而显著增加了问题的复杂性。精确类算法能够求得柔性车间调度问题的最优解，但需要较长的计算时间；近似类算法计算速度较快，但求解效果与最优解存在较大差距。现有算法通常难以在计算时间和求解效果上取得较好的均衡。

技术实现思路

1、本发明的目的在于克服现有技术的不足，提供一种基于下界最小化的柔性作业车间调度方法。

2、本发明的目的是通过以下技术方案实现的：

3、该方法首先进行柔性作业车间调度问题的参数输入；之后基于问题参数求解第一阶段的机器分配，以最小化加工时间下界为优化目标，结合任务独立约束，计算机器分配方案；然后基于求得的机器分配和问题参数求解第二阶段的操作排序，以最小化加工时间为优化目标，结合任务序列约束和操作不重叠约束，求解操作排序方案；最后，结合求得的机器分配结果和操作排序方案，根据调度问题需求整理数据，输出调度方案。

4、1. 一种基于下界最小化的柔性作业车间调度方法，其特征在于：

5、（1）输入柔性作业车间调度参数；

6、（2）以最小化加工时间下界为优化目标，求解机器分配；

7、（3）结合机器分配结果，以最小化加工时间为优化目标，求解操作排序；

8、（4）输出柔性作业车间调度方案。

9、2. 根据权利要求1所述的一种基于下界最小化的柔性作业车间调度方法，其特征在于：所述步骤（1）中的柔性作业车间调度参数输入方法如下：

10、输入柔性作业车间调度中的工作集合相关参数，包括总工作数量，每个工作的标识，及每个工作所包含的任务集合与任务标识；输入柔性作业车间调度中的机器集合相关参数，包括总机器数量，每个机器的标识；输入柔性作业车间调度中的操作集合相关参数，包括特定机器与特定工作的特定任务是否兼容，及兼容情况下所需的加工成本。

11、3. 根据权利要求1所述的一种基于下界最小化的柔性作业车间调度方法，其特征在于：所述步骤（2）中的机器分配阶段求解方法如下：

12、首先，设置机器分配问题的优化目标为最小化加工时间下界。其中，每个工作的总加工成本是其包含的任务的加工成本之和，每个机器的总加工成本是其负责的任务的加工成本之和，加工时间下界被定义为所有工作和机器的总加工成本中的最大值。

13、之后，设置机器分配问题的约束为任务独立约束。其中，每个工作的每个任务都需要分配给兼容的机器进行完成，且每个工作的每个任务至多由一个机器进行完成。

14、然后，将柔性作业车间调度的机器分配问题表示为0-1整数线性规划问题进行求解。其中，问题条件是已知的加工成本集合，中的元素为浮点数，表示使用特定机器加工特定工作中的特定任务所需的加工成本；决策变量是未知的机器分配集合，中的元素取值为0或1，表示是否分配特定机器加工特定工作中的特定任务。在约束条件中，每个任务恰好由一个机器进行加工，该任务对应的所有机器的决策变量之和恰好为1；针对每个工作，其总加工成本的计算方式是对其包含任务的加工成本进行求和，其包含任务的加工成本的计算方式是对任务可选机器的决策变量与相应的加工成本的乘积进行求和；针对每个机器，其总加工成本的计算方式是对可能包含的所有任务的加工成本进行求和，其单个任务的加工成本的计算方式是该任务与该机器共同对应的决策变量与相应的加工成本求乘积。在优化目标中，加工时间下界为一系列工作和机器总成本表达式的最大值，优化方向是最小化目标函数。

15、最后，求解机器分配问题所对应的0-1整数线性规划问题。根据求得的机器分配变量集合中的元素取值，求得最终的机器分配结果。其中，针对某一工作的某一任务及某一机器对应的决策变量，元素取值为1表示使用该机器加工该工作下的该任务。

16、4. 根据权利要求1所述的一种基于下界最小化的柔性作业车间调度方法，其特征在于：所述步骤（3）中的操作排序阶段求解方法如下：

17、首先，设置操作排序问题的优化目标为最小化加工时间。其中，每个工作的每个任务具有各自的加工开始时间和加工结束时间，加工时间被定义为最后完成的工作的最后一个任务的任务结束时间。

18、之后，设置操作排序问题的约束为任务序列约束和操作不重叠约束。其中，每个工作所包含的多个任务需要按顺序进行，后序任务的任务开始时间不早于前序任务的任务结束时间；每个机器所包含的多个操作不能重叠进行，同一机器上不同操作的加工时间段不能重叠。

19、然后，将柔性作业车间调度的操作排序问题表示为混合整数线性规划问题进行求解。其中，问题条件是已知的加工成本集合和已分配的操作集合，中的元素为浮点数，表示使用特定机器加工特定工作中的特定任务所需的加工成本，中的元素是已分配的操作，表示工作包含的任务与机器的分配关系；决策变量是未知的任务开始时间集合和任务结束时间集合，中的元素为浮点数，表示特定工作中的特定任务的加工开始时间，中的元素为浮点数，表示特定工作中的特定任务的加工结束时间。在约束条件中，在已为各个工作的任务分配加工机器的情况下，各任务的任务结束时间与任务开始时间之差等于该操作的加工成本；由于每个工作的不同任务依次进行，同一工作中后序任务的任务开始时间大于等于前序任务的任务结束时间；各个机器所包含的操作不重叠，针对同一机器上的任意两个操作，恰好存在某个操作的任务开始时间不早于另一个操作的任务结束时间。在优化目标中，加工时间为所有工作包含任务中的任务结束时间最大值，优化方向是最小化目标函数。

20、最后，求解操作排序问题所对应的混合整数线性规划问题。根据求得的各工作中各任务的任务开始时间和任务结束时间，求得最终的操作排序结果。其中，针对同一机器上所包含的各个操作，具有更小的任务开始时间的操作优先执行。

21、5. 根据权利要求1所述的一种基于下界最小化的柔性作业车间调度方法，其特征在于：所述步骤（4）中的柔性作业车间调度方案输出方法如下：

22、结合求得的机器分配结果和操作排序结果，依据柔性车间调度的问题需求，整理得到最终的柔性车间调度方案进行输出。其中，最终的柔性车间调度方案通常以列表或甘特图的形式呈现，列表及甘特图中的元素可包括操作对应的工作索引，操作对应的任务索引，操作对应的机器索引，操作加工开始时间，操作加工结束时间等信息。

23、本发明的上述技术方案的有益效果如下：

24、上述方案中，该方法首先进行柔性作业车间调度参数的输入；之后结合问题参数，以最小化加工时间下界为优化目标，求解调度方案中的机器分配部分；然后结合问题参数和机器分配方案，以最小化加工时间为优化目标，求解调度方案中的操作排序部分；最后结合求解的机器分配方案和操作排序方案，生成并输出完整的调度方案。本发明分两阶段对柔性作业车间调度问题进行求解，使用加工时间下界作为第一阶段的优化目标，将机器分配阶段建模为0-1整数线性规划问题，将操作排序阶段建模为混合整数线性规划问题，简化了柔性作业车间调度问题的求解复杂度，减少了求解过程中涉及的决策变量和约束数量。基于柔性作业车间调度问题中加工时间下界与加工时间的强关联性，本发明能够保持调度方案较高的求解质量，同时显著提高柔性作业车间调度问题的计算效率。