基于改进IG算法的考虑交付时间窗和机器准备时间的混合流水车间调度研究  

Research on Hybrid Flow-shop Scheduling Considering Delivery Time Windows and Machine Setup Times Based on an Improved IG Algorithm

作　　者：王建华[1] 曹一雷 邱荣根 WANG Jian-hua;CAO Yi-lei;QIU Rong-gen(School of Management,Jiangsu University,Zhenjiang 212013,China)

机构地区：[1]江苏大学管理学院,江苏镇江212013

出　　处：《物流工程与管理》2024年第12期46-49,共4页Logistics Engineering and Management

基　　金：江苏大学高级人才科研启动基金项目(11JDG006)。

摘　　要：针对考虑交付时间窗和机器准备时间的混合流水车间调度问题,以最小化完工时间和最小化提前与拖期加权总和为优化目标,建立混合整数线性规划模型,并根据问题设计一种无参数迭代贪婪算法(IIG)。在IIG算法中,首先通过三种常用于最小化提前和延迟目标的启发式方法生成解,保留这三者中最优的解作为初始解;其次,采用不需要销毁参数的自适应销毁策略,按照贪婪规则跳过位置,+-避免非改进插入位置的重构方法;然后,使用邻域插入的局部搜索;接着,采用一种与锦标赛算法类似的接受准则来强化对当前解的局部搜索;最后将IIG与NSGA-II、JAYA、TLBO以及PSO四种算法进行270个实例实验分析比较,验证了IIG算法的有效性。This study addresses the hybrid flow-shop scheduling problem(HFSP)that incorporating delivery time windows and machine setup times,with the objective of minimizing+both makespan and the weighted sum of earliness and tardiness,and establishes a mixed-integer linear programming(MILP)model while designs a parameter-free iterative greedy algorithm(IIG)according to the problem.In the IIG algorithm,firstly,utilizing three common heuristics for minimizing earliness and tardiness to generate solutions,selecting the best one as the initial solution.Secondly,an adaptive destruction strategy is employed that avoids the need for parameter destruction,using greedy rules to skip positions and prevent the reconstruction of non-improving insertion sites.Then,local search is performed through neighborhood insertion,followed by a tournament-like acceptance criterion to enhance the local search of the current solution.At last,the effectiveness of the IIG algorithm is validated through comparative experimental analysis against four other algorithms—NSGA-II,JAYA,TLBO,and PSO—across 270 instances,demonstrating its robust performance.

关 键 词：混合流水车间调度 序列相关准备时间:交付时间窗 IG算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TB497[自动化与计算机技术—控制科学与工程]