Automatic Design Of Rules For Hybrid Flow Shops With Batch Processing Machines

The production mode of the equipment manufacturing industry in China shares a characteristic of high variety and small quantity. A variant of the standard hybrid flow shop(HFS) scheduling problem is studied by adding constraints like complex processing routes and multiple machine types to it. A genetic programming and ant colony optimization-based automatic rule design(AGRD) approach is proposed for it.Firstly, with the knowkedge of the industrial environments, a k-stage( k?3) HFS scheduling problem with batch processing machines is described and mathematically formulated.Secondly, because it is hard to solve a NP-hard problem like the addressed one, it is decomposed into three sub-problems to lower the complexity, i.e. part assignment, part sequencing and batch formation. A two-stage automatic rule design(AGRD) approach is proposed to solve the different sub-problems altogether. In the first phase of AGRD, a genetic programming(GP) algorithm is employed to evolve heuristic rules which then extend the candidate rule set. A candidate rule set, of which half is composed of the evolved heuristic rules and the rest consists of the existing heuristic rules is constructed. In the second phase, an ant colony optimization(ACO) algorithm is used to select a rule for each part, single processing machine or batch processing machine.Thirdly, when generating solutions, a modified look-ahead time window(MLTW) strategy, which defines the waiting time during which parts are allowed to be added to the batch on a batch processing machine, is designed. In case that a batch on a batch processing machine is not full, it is assigned a time window.Finally, a series of comparison experiments are conducted. It turns out that: i) by the adoption of rules evolved by the GP algorithm, the performance the AGRD approach is improved; ii) the ACO algorithm is able to select good combinatorial rules; iii) the use of the time window strategy helps to make a balance between the solution quality and the utilization rate of batch processing machines; iv) the comparison with a similar approach shows that AGRD is well designed owing to the following two reasons: 1) the real-time information of parts or machines are adopted as terminals of the GP algorithm, which designs good rules for the problem; 2) when selecting rules for machines, the distinction between different machines are considered. AGRD is therefore suitable for manufacturing environments in practice; v) both the comparisons with the approach in a similar problem and CPLEX show the effectiveness of AGRD.