TY - JOUR
T1 - Population-based Tabu search with evolutionary strategies for permutation flow shop scheduling problems under effects of position-dependent learning and linear deterioration
AU - Arık, Oğuzhan Ahmet
N1 - Springer deal
PY - 2020/8/7
Y1 - 2020/8/7
N2 - This paper investigates permutation flow shop scheduling (PFSS) problems under the effects of position-dependent learning and linear deterioration. In a PFSS problem, there are n jobs and m machines in series. Jobs are separated into operations on m different machines in series, and jobs have to follow the same machine order with the same sequence. The PFSS problem under the effects of learning and deterioration is introduced with a mixed-integer nonlinear programming model. The time requirement for solving large-scale problems type of PFSS problem is exceedingly high. Therefore, well-known metaheuristic methods for the PFSS problem without learning and deterioration effects such as iterated greedy algorithms and discrete differential evolution algorithm are adapted for the problem with learning and deterioration effects in order to find a faster and near-optimal or optimal solution for the problem. Furthermore, this paper proposes a hybrid solution algorithm that is called population-based Tabu search algorithm (TSPOP) with evolutionary strategies such as crossover and mutation. The search algorithm is built on the basic structure of Tabu search and it searches for the best candidate from a solution population instead of improving the current best candidate at each iteration. Furthermore, the performances of these methods in view of solution quality are discussed in this paper by using test problems for 20, 50, and 100 jobs with 5, 10, 20 machines. Experimental results show that the proposed TSPOP algorithm outperforms the other existing algorithms in view of solution quality.
AB - This paper investigates permutation flow shop scheduling (PFSS) problems under the effects of position-dependent learning and linear deterioration. In a PFSS problem, there are n jobs and m machines in series. Jobs are separated into operations on m different machines in series, and jobs have to follow the same machine order with the same sequence. The PFSS problem under the effects of learning and deterioration is introduced with a mixed-integer nonlinear programming model. The time requirement for solving large-scale problems type of PFSS problem is exceedingly high. Therefore, well-known metaheuristic methods for the PFSS problem without learning and deterioration effects such as iterated greedy algorithms and discrete differential evolution algorithm are adapted for the problem with learning and deterioration effects in order to find a faster and near-optimal or optimal solution for the problem. Furthermore, this paper proposes a hybrid solution algorithm that is called population-based Tabu search algorithm (TSPOP) with evolutionary strategies such as crossover and mutation. The search algorithm is built on the basic structure of Tabu search and it searches for the best candidate from a solution population instead of improving the current best candidate at each iteration. Furthermore, the performances of these methods in view of solution quality are discussed in this paper by using test problems for 20, 50, and 100 jobs with 5, 10, 20 machines. Experimental results show that the proposed TSPOP algorithm outperforms the other existing algorithms in view of solution quality.
KW - UT-Hybrid-D
KW - Discrete differential equation
KW - Evolutionary strategy
KW - Iterated greedy
KW - Learning effect
KW - Makespan
KW - Permutation flow shop scheduling
KW - Tabu search
KW - Deterioration effect
UR - http://www.scopus.com/inward/record.url?scp=85089194284&partnerID=8YFLogxK
U2 - 10.1007/s00500-020-05234-7
DO - 10.1007/s00500-020-05234-7
M3 - Article
AN - SCOPUS:85089194284
JO - Soft computing
JF - Soft computing
SN - 1432-7643
ER -