Flower Pollination Algorithm Based on Block Structure Properties for Reentrant Job Shop Scheduling Problem

doi:10.3901/JME.2019.16.220

Abstract

Abstract: Flower pollination algorithm based on block structure properties (FPA_BSP) is presented to minimize the total weighted tardiness (TWT) for reentrant job shop scheduling problem (RJSSP). Firstly, the mathematical model of RJSSP based on the disjunctive graph is established, and then its duality model is proved to be the model of maximum cost flow problem after it being determined the direction of the disjunctive arcs. Secondly, the extended reentrant-smallest-order-value (RSOV) encoding rule is designed to transform FPA's individuals from real vectors to job permutations so that flower pollination algorithm (FPA) can be used to perform global search for finding high-quality solutions or regions in the solution space. Thirdly, eight kinds of neighborhood structures are defined, and the inner properties of block structures are analyzed based upon the properties of the maximum cost flow problem. The determination conditions of the four former neighborhood structures for improving TWT are obtained by the block structures' analyses, which can be used to avoid search in the invalid regions. Then, a high-efficient local search integrating multiple neighborhoods with the obtained determination conditions is proposed to execute a thorough search from the promising regions found by the global search. Computational experiments and comparisons manifest the effectiveness of the presented FPA_BSP. The properties of RJSSP's block structures and incorporates them with FPA are proposed to obtain an effective FPA_BSP for solving RJSSP. It is also the first time that FPA is used to address scheduling problem.

Key words: block structure properties, flower pollination algorithm, reentrant job shop scheduling problem, total weighted tardiness

CLC Number:

TG156

SUN Zaixing, QIAN Bin, HU Rong, ZHANG Ziqi, ZHANG Changsheng. Flower Pollination Algorithm Based on Block Structure Properties for Reentrant Job Shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2019, 55(16): 220-232.

References

[1] 潘全科,王凌,高亮,等. 基于差分进化与块结构邻域的作业车间调度优化[J]. 机械工程学报,2010,46(22):182-188. PAN Quanke,WANG Ling,GAO Liang,et al. Differential evolution algorithm based on blocks on critical path for job shop scheduling problems[J]. Journal of Mechanical Engineering,2010,46(22):182-188.
[2] GAREY M R,JOHNSON D S,SETHI R. The complexity of flowshop and jobshop scheduling[J]. Mathematics of Operations Research,1976,1(2):117-129.
[3] 唐国春,张峰,罗守成,等. 现代排序论[M]. 上海:上海科学普及出版社,2003. TANG Guochun,ZHANG Feng,LUO Shoucheng,et al. Modern scheduling theory[M]. Shanghai:Shanghai Popular Science Press,2003.
[4] VAN LAARHOVEN P J M,AARTS E H L,LENSTRA J K. Job shop scheduling by simulated annealing[J]. Operations Research,1988, 40(1):113-125.
[5] BALAS E. Machine sequencing via disjunctive graphs:an implicit enumeration algorithm[J]. Operations Research,1969,17(17):941-957.
[6] MATSUO H,SUH C J,SULLIVAN R S. A controlled search simulated annealing method for the general job-shop scheduling problem[J]. Annals of Operations Research,1988,21(1):85-108.
[7] GRABOWSKI J,NOWICKI E,SMUTNICKI C. Block algorithm for scheduling operations in a job-shop system[J]. Przeglad Statystyczny,1988,35(1):67-80.
[8] GRABOWSKI J,NOWICKI E,ZDRZALKA S. A block approach for single-machine scheduling with release dates and due dates[J]. European Journal of Operational Research,1986,26(2):278-285.
[9] DELL'AMICO M,TRUBIAN M. Applying tabu search to the job-shop scheduling problem[J]. Annals of Operations Research,1993,41(3):231-252.
[10] NOWICKI E,SMUTNICKI C. A fast taboo search algorithm for the job shop problem[J]. Management Science,1996,42(6):797-813.
[11] BALAS E,VAZACOPOULOS A. Guided local search with shifting bottleneck for job shop scheduling[J]. Management Science,1998,44(2):262-275.
[12] ZHANG C Y,LI P G,GUAN Z L,et al. A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem[J]. Computers & Operations Research,2007,34(11):3229-3242.
[13] ZHANG R,WU C. A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective[J]. Computers & Operations Research,2011,38(5):854-867.
[14] KUHPFAHL J,BIERWIRTH C. A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective[J]. Computers & Operations Research,2016,66:44-57.
[15] 赵诗奎. 基于新型邻域结构的混合算法求解作业车间调度[J]. 机械工程学报,2016,52(9):141-151. ZHAO Shikui. A hybrid algorithm with a new neighborhood structure for the job shop scheduling problem[J]. Journal of Mechanical Engineering,2016,52(9):141-151.
[16] TOPALOGLU S,KILINCLI G. A modified shifting bottleneck heuristic for the reentrant job shop scheduling problem with makespan minimization[J]. International Journal of Advanced Manufacturing Technology,2009,44(7-8):781-794.
[17] QIAN B,LI Z H,HU R,et al. A hybrid differential evolution algorithm for the multi-objective reentrant job-shop scheduling problem[C]//10th IEEE International Conference on Control and Automation (ICCA),Hangzhou,2013:485-489.
[18] CHEN S F,QIAN B,LIU B,et al. Bayesian statistical inference-based estimation of distribution algorithm for the re-entrant job-shop scheduling problem with sequence-dependent setup times[C]//10th International Conference on Intelligent Computing (ICIC),Taiyuan,2014. Lecture Notes in Computer Science, Springer, Cham,2014,(8589):686-696.
[19] YANG X S. Flower pollination algorithm for global optimization[C]//International Conference on Unconventional Computation and Natural Computation. Springer-Verlag,2012:240-249.
[20] WENNINK M. Algorithmic support for automated planning boards[D]. Eindhoven,Netherlands:Technische Universiteit Eindhoven,1995.
[21] KURDI M. An effective new island model genetic algorithm for job shop scheduling problem[J]. Computers & Operations Research,2016,67:132-142.