Processing time tolerance-based ACO algorithm for solving job-shop scheduling problem

3rd International Conference on Advances in Energy, Environment and Chemical Engineering

能源学;生态环境科学;化学工业

Luo, Yabo^1 ; Waden, Yongo P.^1

School of Mechanical and Electronic Engineering, Wuhan University of Technology, Wuhan city

430070, China^1

关键词: Ant Colony Optimization algorithms;    Bench-mark problems;    Comparative experiments;    Constraint handling;    Job shop scheduling problems;    Model-based OPC;    Processing time;    Uncertainty and complexity;   

Others  :  https://iopscience.iop.org/article/10.1088/1755-1315/69/1/012181/pdf
DOI  :  10.1088/1755-1315/69/1/012181

学科分类：环境科学（综合）

来源: IOP

【 摘 要 】

Ordinarily, Job Shop Scheduling Problem (JSSP) is known as NP-hard problem which has uncertainty and complexity that cannot be handled by a linear method. Thus, currently studies on JSSP are concentrated mainly on applying different methods of improving the heuristics for optimizing the JSSP. However, there still exist many problems for efficient optimization in the JSSP, namely, low efficiency and poor reliability, which can easily trap the optimization process of JSSP into local optima. Therefore, to solve this problem, a study on Ant Colony Optimization (ACO) algorithm combined with constraint handling tactics is carried out in this paper. Further, the problem is subdivided into three parts: (1) Analysis of processing time tolerance-based constraint features in the JSSP which is performed by the constraint satisfying model; (2) Satisfying the constraints by considering the consistency technology and the constraint spreading algorithm in order to improve the performance of ACO algorithm. Hence, the JSSP model based on the improved ACO algorithm is constructed; (3) The effectiveness of the proposed method based on reliability and efficiency is shown through comparative experiments which are performed on benchmark problems. Consequently, the results obtained by the proposed method are better, and the applied technique can be used in optimizing JSSP.