Cross Process Coordinated Scheduling Problem Based on Hybrid Discrete Bat Algorithm

Abstract

Abstract: Aiming at the problem of collaborative scheduling of production and distribution across processes, a collaborative scheduling model of single-machine batch processing in former process and order-by-order processing in latter process was constructed, and AGV circular distribution was adopted among the processes. A hybrid discrete bat algorithm, which is combined with simulated annealing algorithm and modified unstring and string algorithm, was designed to minimize the maximum completion time and waiting time before subsequent process. Compared with the improved discrete particle swarm optimization and Ullrich genetic algorithm, the proposed algorithm may reduce queue waiting time and production cycle of products.

Key words: coordinated scheduling, cross process, hybrid discrete bat algorithm；automated guided vehicle(AGV)

摘要： 针对跨工序的生产与配送协同调度问题，构建了前工序单机批加工、后工序多产线逐订单加工，且工序之间采用自动引导车循环配送的协同调度模型。以最小化最大完工时间和后工序前的在制品等待时间为调度目标，设计了融合模拟退火算法与解串算法的混合离散蝙蝠算法，与改进的离散粒子群算法和Ullrich遗传算法相比，该算法能很好地减少后工序产线前的队列等待时间，缩短产品的生产周期。

关键词: 协同调度, 跨工序, 混合离散蝙蝠算法, 自动引导车

CLC Number:

TP242

LU Jiansha1,2;LI Jinqing1;TANG Hongtao1. Cross Process Coordinated Scheduling Problem Based on Hybrid Discrete Bat Algorithm[J]. China Mechanical Engineering.

鲁建厦1,2;李晋青1;汤洪涛1. 基于混合离散蝙蝠算法的跨工序协同调度问题[J]. 中国机械工程.

References

[1]MAGGU P L, DAS G. On 2×n Sequencing Problem with Transportation Times of Jobs[J]. Pure and Applied Mathematica, Science, 1980,129(12):1-6.

[2]ARMENTANO V A, SHIGUEMOTO A L, LKKETANGEN A. Tabu Search with Path Relinking for an Integrated Production-distribution Problem[J]. Computers ＆ Operations Research, 2011,38(1):320-327.

[3]方伯芃, 孙林夫. 不确定环境下产业链生产与配送协同调度优化[J]. 计算机集成制造系统, 2018, 24(1):224-244.

FANG Bopeng, SUN Linfu. Coordinated Scheduling Optimization of Production and Distribution of Industrial Chain under Uncertain Environment[J]. Computer Integrated Manufacturing System, 2018, 24(1): 224-244.

[4]李凯, 王明星. 单机多车情形生产与配送协同调度算法[J]. 计算机集成制造系统, 2014, 20(12):3011-3019.

LI Kai, WANG Mingxing. Coordinated Scheduling Algorithm of Production and Distribution in the Case of Single Machine and Multi-vehicle[J]. Computer Integrated Manufacturing System, 2014, 20(12):3011-3019.

[5]关静, 唐立新. 工件带有温降的生产与前运输协调调度问题[J]. 系统工程学报, 2007, 22(6):639-643.

GUAN Jing, TANG Lixin. Inbound Transportation and Production Coordinated Scheduling Problem with Temperature Reduction Jobs[J]. Journal of Systems & Management, 2007, 22(6):639-643.

[6]马文琼, 王凯. 两阶段装配流水车间加工与配送协同调度研究[J]. 工业工程与管理, 2016, 21(6):103-117.

MA Wenqiong, WANG Kai. Coordinated Scheduling Problem for Two-stage Assembly Flowshop Production and Distribution[J]. Industrial Engineering and Management, 2016, 21(6):103-117.

[7]刘玲. 单机器生产与车辆路径协同调度问题建模与算法研究[D]. 武汉:华中科技大学, 2016.

LIU Ling. Model and Algorithms for the Integrated Single Machine Scheduling and Vehicle Routing Problem[D]. Wuhan: Huazhong University of Science and Technology, 2016.

[8]卓雪雪. 批处理机环境下两阶段集成调度算法研究[D]. 合肥:安徽大学,2018.

ZHUO Xuexue. Research on Batch Scheduling Processing on Parallel Machines with Two-stage Integrated Scheduling[D]. Hefei: Anhui University, 2018.

[9]YANG X S. A New Metaheuristic Bat-inspired Algorithm[M]//Nature Inspired Cooperative Strategies for Optimization (NICSO2010). Berlin：Springer, 2010:65-74.

[10]LI K, CHEN B, SIVAKUMAR A I, et al. An Inventory-routing Problem with the Objective of Travel Time Minimization[J]. European Journal of Operational Research, 2014, 236(3):936-945.

[11]薛梅, 周志平. 批处理机环境下生产与两阶段运输协同调度问题研究[J]. 中国管理科学, 2016, 24:22-28.

XUE Mei, Zhou Zhiping. Coordinated Scheduling Problem of Production and Two-stage Transportation with a Batch-processing Machine[J]. Chinese Journal of Management Science, 2016, 24:22-28.

[12]ULLRICH C A. Integrated Machine Scheduling and Vehicle Routing with Time Windows[J]. European Journal of Operational Research, 2013, 227(1): 152-165.

[13]尹建津, 张贝克. 改进蝙蝠算法解决FFSP问题及其应用研究[J]. 计算机工程应用, 2019, 55(9):243-247.

YIN Jianjin, ZHANG Beike. Improved Bat Algorithm for Solving Flexible Flow Shop Scheduling Problem and Its Application[J]. Computer Engineering and Applications, 2019, 55(9):243-247.

[14]徐华, 张庭. 混合离散蝙蝠算法求解多目标柔性作业车间调度[J]. 机械工程学报, 2016,52(18):201-212.

XU Hua, ZHANG Ting. Hybrid Discrete Bat Algorithm for Solving the Multi-objective Flexible JobShop Scheduling Problem[J]. Journal of Mechanical Engineering, 2016,52(18):201-212.

[15]韩忠华, 朱伯秋. 基于改进蝙蝠算法的柔性流水车间排产优化问题研究[J]. 计算机应用研究, 2017, 34(7): 1935-1938.

HAN Zhonghua, ZHU Boqiu. Study for Flexible Flow Shop Scheduling Problem Based on Advanced Bat Algorithm[J]. Application Research of Computer, 2017, 34(7): 1935-1938.

[16]刘玲, 李昆鹏. 生产和运输协同调度问题的模型和算法[J]. 工业工程与管理, 2016,21(2):86-91.

LIU Ling, Li Kunpeng. Model and Algorithms for the Integrated Production and Transportation Scheduling[J]. Industrial Engineering and Managemen, 2016, 21(2): 86-91.

[17]李修琳, 鲁建厦. 基于混合遗传算法的混流混合车间协同调度问题[J]. 中国机械工程, 2012, 23(8):935-940.

LI Xiulin, LU Jiansha. Hybrid Genetic Algorithm for Mixed-model Hybrid-shop Scheduling Problem[J]. China Mechanical Engineering, 2012, 23(8):935-940.