Discrete differential evolution algorithm for distributed blocking flowshop scheduling with makespan criterion. (November 2018)

• Record Type: Journal Article
• Authors: Zhang, Guanghui; Xing, Keyi; Cao, Feng
• Is Part Of: Engineering applications of artificial intelligence. Volume 76(2018)
• Page Start: 96
• Page End: 107
• Publication Date: 2018-11
• Subjects: Scheduling -- Distributed blocking flowshop -- Makespan -- Mathematical model -- Discrete differential evolution algorithm; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2018.09.005
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: This paper deals with a distributed blocking flowshop scheduling problem, which tries to solve the blocking flowshop scheduling in distributed manufacturing environment. The optimization objective is to find a suitable schedule, consisting of assigning jobs to at least two factories and sequencing the jobs assigned to each factory, to make the maximum completion time or makespan minimization. Two different mathematical models are proposed, and in view of the NP-hardness of the problem, a novel hybrid discrete differential evolution (DDE) algorithm is established. First, the problem solution is represented as several job permutations, each of which denotes the partial schedule at a certain factory. Second, four widely applied heuristics are generalized to the distributed environment for providing better initial solutions. Third, both operators of mutation and crossover are redesigned to perform the DDE directly based on the discrete permutations, and a biased section operator is used to increase the diversity of the searching information. Meanwhile, an effective local search based on distributed characteristics and an elitist retain strategy are integrated into the DDE framework to stress both local exploitation and global exploration. Taking into account the time cost, an effective speed-up technique is designed to enhance the algorithmic efficiency. In the experimental section, the parameters of DDE are calibrated by the Taguchi method. Experimental results derived from a wealth of test instances have demonstrated the algorithmic effectiveness, which further concludes that the proposed DDE algorithm is a suitable alternative approach for solving the problem under consideration. Highlights: A distributed blocking flowshop scheduling problem is solved by meta-heuristics. A discrete differential evolution is developed by discreteness and distribution. New evolutionary operators are designed to perform DDE directly on discrete domain. An efficient local search with speed-up evaluation is integrated into DDE framework. The algorithmic performance is validated from both search quality and efficiency.