A new algorithm based on evolutionary computation for hierarchically coupled constraint optimization: methodology and application to assembly job-shop scheduling

摘要

Hierarchically coupled constraint optimization (HCCO) problems are omnipresent, both in theoretical problems and in real-life scenarios; however, there is no clear definition to identify these problems. Numerous techniques have been developed for some typical HCCO problems, such as assembly job-shop scheduling problems (AJSSPs); however, these techniques are not universally applicable to all HCCO problems. In this paper, an abstract definition and common principles amongst different HCCO problems are first established. Next, based on the definitions and principles, a new optimization algorithm based on evolutionary computation is developed for HCCO. The new optimization algorithm has three key new features: a new initial solution generator, a level barrier-based crossover operator, and a level barrier-based mutation operator. In the initial solution generator, a partial solution is created in the first step that satisfies the lowest level hierarchically coupled constraint (HCC) and each consecutive step afterwards adds on to the partial solution to satisfy the next higher level of HCC. In the level barrier-based operators, the operations are only performed between genes satisfying the same level of HCCs to ensure feasibility of the new solutions. The developed optimization algorithm is used to solve a variety of AJSSPs and the results obtained using the proposed algorithm are compared to other methods used to solve AJSSPs.