基于混合整数线性规划的人机协作柔性流水车间调度问题集成优化框架

Integrated Optimization Framework for Human-Machine Collaborative Flexible Flow Shop Scheduling Based on Mixed-Integer Linear Programming

  • 摘要: 人机协作(human-machine collaboration,HMC)是一种具有广阔前景和重要性的生产模型,它同时结合了工人柔性优点和机器高效率的优点. 为了获取最优精确解,针对人机协作柔性流水车间调度问题(human-machine collaborative flexible flow shop scheduling problem,HMC-FFSP)建立了一个基于混合整数线性规划(mixed-integer linear programming,MILP)的集成优化框架,包含了3种建模思想:相邻序列建模思想、序列建模思想、时间建模思想,其中序列建模思想有2个变种. 首先分析了HMC-FFSP问题特性,然后基于不同建模思想,通过设计不同离散决策变量、连续决策变量及约束集,构建了4种MILP模型. 本文还设计了小规模和大规模算例,并从规模复杂度和计算复杂度2个方面来对比这些MILP模型,例如0-1布尔决策变量、连续决策变量、求解时间、约束总数等. 实验结果验证了所提出的4种MILP在求解HMC-FFSP问题的可行性和有效性,并发现基于序列的建模思想表现最优,基于相邻序列的建模模型表现次之,基于时间的建模思想表现最差. 最后,对实验结果进行了Wilcoxon符号秩检验和配对样本t检验等统计学分析,进一步增强了结论的可靠性.

     

    Abstract: Human-machine collaboration (HMC) is a promising and important production model that combines the advantages of worker flexibility and machine efficiency. To obtain an optimal and exact solution, an integrated optimization framework based on mixed-integer linear programming (MILP) was established for the human-machine collaborative flexible flow shop scheduling problem (HMC-FFSP), which included three modeling ideas: adjacent sequence-based modeling idea, sequence-based modeling idea, and time-based modeling idea, with the sequence-based modelling idea further consisting of two variants. Firstly, the characteristics of the HMC-FFSP problem were analyzed, and then based on different modeling ideas, four MILP models were finally established through designing different discrete decision variables, continuous decision variables, and different constraint sets. In addition, small-scale and large-scale test instances were also designed, and those MILP models were compared from two aspects: size complexity and computational complexity, such as 0-1 Boolean decision variables, continuous decision variables, solution time, total number of constraints, and so on. Experimental results verified the feasibility and effectiveness of the four proposed MILP models in solving HMC-FFSP problems, and revealed that the sequence based modeling idea achieved the best performance, followed by the adjacent sequence-based modeling idea, while the time-based modeling idea performed the worst. Finally, statistical analyses, including the Wilcoxon signed-rank test and paired sample t-test, were conducted on the experimental results, further enhancing the reliability of the conclusion.

     

/

返回文章
返回
Baidu
map