An Adaptive Scheduling Algorithm for Dynamic Jobs for Dealing with the Flexible Job Shop Scheduling Problem

摘要

Modern manufacturing systems build on an effective scheduling scheme that makes full use of the system resource to increase the production, in which an important aspect is how to minimize the makespan for a certain production task(i.e., the time that elapses from the start of work to the end) in order to achieve the economic profit. This can be a difficult problem, especially when the production flow is complicated and production tasks may suddenly change. As a consequence, exact approaches are not able to schedule the production in a short time. In this paper, an adaptive scheduling algorithm is proposed to address the makespan minimization in the dynamic job shop scheduling problem. Instead of a linear order, the directed acyclic graph is used to represent the complex precedence constraints among operations in jobs. Inspired by the heterogeneous earliest finish time(HEFT) algorithm, the adaptive scheduling algorithm can make some fast adaptations on the fly to accommodate new jobs which continuously arrive in a manufacturing system. The performance of the proposed adaptive HEFT algorithm is compared with other state-of-the-art algorithms and further heuristic methods for minimizing the makespan. Extensive experimental results demonstrate the high efficiency of the proposed approach.