A filter search algorithm based on machine-order space for job-shop scheduling problems

Abstract

Purpose - The research aims to develop a practicable method to solve relatively large job-shop scheduling problems (JSSP) for production planning in real-time. Design/methodology/approach - This paper analyses some search strategies based on machine-order space, and proposes a filter search algorithm (FSA) to reduce computing time by improving the speed of finding a proper machine order. Numerical experiments are conducted to verify the FSA. Findings - The experiments confirmed the superior performance of the FSA, making it possible to solve relatively large JSSPs in real-time. The results showed that the leaf-node number affects the solution quality. The performance can be improved by increasing the leaf-node number. There is a significant decrease in the average quality deviation when the leaf-node number increases; but the decreasing rate becomes minor when the leaf-node number is relatively large. While triple filters may provide more leaf-node numbers for the FSA, dual filters are considered enough for most practical scheduling problems. A method is proposed to determine appropriate leaf-node numbers for practical production environments. Research limitations/implications - A limitation is that the FSA's performance is affected by the choice of leaf-node number. Although the relationships between the solution quality and the leaf-node number for some problems have been worked out, it will be useful future research to deduce the relationships for other job-shop instances of different sizes. Originality/value - The FSA is a new approach, which is particularly useful for planning production schedules needed for efficient and responsive management of manufacturing systems to cope with increasing global competition and market changes. © Emerald Group Publishing Limited.