期刊名称：International Journal of Advances in Soft Computing and Its Applications
印刷版ISSN：2074-8523
出版年度：2016
卷号：8
期号：2
出版社：International Center for Scientific Research and Studies
摘要：The job shop scheduling problem (JSSP) is regarded as one of the problems which is widely studied. This paper presents a bee colony optimization (BCO) algorithm with a local search named the modified two-enhancement scheme with neighbourhood N5 perturbation (BCO+mTESN5) to solve the JSSP. In previous research, the BCO algorithm with TESN5 local search (BCO+TESN5) is applied to solve the JSSP. The BCO+TESN5 algorithm uses a brute force strategy in performing the N5 neighbourhood local search. However, the brute force local search strategy incurs expensive overhead. To address the high overhead issue, the BCO+mTESN5 algorithm is proposed where the local search is performed on a targeted bottleneck machine within the N5 neighbourhood structure. The selection of the targeted bottleneck machine is done based on a list of bottleneck machines identified by the shifting bottleneck heuristic (SBH). Two selection strategies are tested to select the targeted bottleneck machine, namely: the greedy selection and the linear ranking selection. The proposed algorithms are examined using a set of benchmark problems obtained from the OR-library. The results show that the proposed BCO+mTESN5 with linear ranking selection successfully solves 54% of the 82 OR-library benchmark dataset to ≤ 1% from known optimum and it is comparable to the BCO+TESN5 algorithm. In terms of computational time to obtain the best makespan, the proposed BCO+mTESN5 with linear ranking selection outperforms the BCO+TESN5 algorithm by 25%.
