Effective Constructive Heuristic and Metaheuristic for the Distributed Assembly Blocking Flow-shop Scheduling Problem

摘要

Scheduling in distributed production system has become an active research field in recent years. This paper investigates the distributed assembly blocking flow-shop scheduling problem (DABFSP), which consists of two stages: production and assembly. The first stage is processing jobs in several identical factories. Each factory has a series of machines no intermediate buffers existing between adjacent ones. The second stage assembles the processed jobs into the final products through a single machine. The objective is to minimize the maximum completion time or makespan of all products. To address this problem, a constructive heuristic is proposed based on a new assignment rule of jobs and a product-based insertion procedure. Afterwards, an iterated local search (ILS) is presented, which integrates an integrated encoding scheme, a multi-type perturbation procedure containing four kinds of perturbed operators based on problem-specific knowledge and a critical-job-based variable neighborhood search. Finally, a comprehensive computational experiment and comparisons with the closely related and well performing methods in the literature are carried out. The experimental and comparison results show that the proposed constructive heuristic and ILS can solve the DABFSP effectively and efficiently.