A decomposition heuristics based on multi-bottleneck machines for large-scale job shop scheduling problems
Abstract: A decomposition
heuristics based on multi-bottleneck machines for large-scale job shop
scheduling problems (JSP) is proposed.
Design/methodology/approach: In the algorithm, a number of sub-problems
are constructed by iteratively decomposing the large-scale JSP according to the
process route of each job. And then the solution of the large-scale JSP can be
obtained by iteratively solving the sub-problems. In order to improve the
sub-problems' solving efficiency and the solution quality, a detection method
for multi-bottleneck machines based on critical path is proposed. Therewith the
unscheduled operations can be decomposed into bottleneck operations and
non-bottleneck operations. According to the principle of “Bottleneck leads the
performance of the whole manufacturing system” in TOC (Theory Of Constraints),
the bottleneck operations are scheduled by genetic algorithm for high solution
quality, and the non-bottleneck operations are scheduled by dispatching rules
for the improvement of the solving efficiency.
Findings: In the process of the sub-problems' construction, partial
operations in the previous scheduled sub-problem are divided into the
successive sub-problem for re-optimization. This strategy can improve the
solution quality of the algorithm. In the process of solving the sub-problems,
the strategy that evaluating the chromosome's fitness by predicting the global
scheduling objective value can improve the solution quality.
Research limitations/implications: In this research, there are some
assumptions which reduce the complexity of the large-scale scheduling problem.
They are as follows: The processing route of each job is predetermined, and the
processing time of each operation is fixed. There is no machine breakdown, and
no preemption of the operations is allowed. The assumptions should be
considered if the algorithm is used in the actual job shop.
Originality/value: The research provides an efficient scheduling method
for the large-scale job shops, and will be helpful for the discrete
manufacturing industry for improving the production efficiency and
effectiveness.
Author: Yingni Zhai, Changjun
Liu, Wei Chu, Ruifeng Guo, Cunliang Liu
Journal Code: jptindustrigg140092
