Browsing by Author "Gao, Liang"

Now showing 1 - 9 of 9

Citation - WoS: 8
Citation - Scopus: 11
A Discrete Artificial Bee Colony Algorithm for the Energy-Efficient No-Wait Flowshop Scheduling Problem
(ELSEVIER SCIENCE BV, 2019) M. Fatih Tasgetiren; Damla Yuksel; Liang Gao; Quan-Ke Pan; Peigen Li; Yuksel, Damla; Tasgetiren, M. Fatih; Gao, Liang; Li, Peigen; Fatih Tasgetiren, M.; Pan, Quan-Ke; CH Dagli; GA Suer
No-wait permutation flow shop scheduling problem (NWPFSP) is a variant of permutation flow shop scheduling problem (PFSP) where the processing of each job must be continuous from start to end without any interruption. That is once a job starts its processing it has to be processed until the last machine without any interruption. The aim of this study is to propose an energy-efficient NWPFSP for the determination of a trade-off between total flow time and total energy consumption by obtaining the Pareto optimal set that is the non-dominated solution set. A bi-objective mixed-integer programming model is developed where the machines can operate at different speed levels. Since the problem is NP-complete an energy-efficient discrete artificial bee colony (DABC) and an energy-efficient genetic algorithm (MOGA) also a variant of this algorithm (MOGALS) are developed as heuristic methods. First the performance of these algorithms for comparison with the mathematical model is represented in small size instances in the scope of cardinality and quality of the non-dominated solutions then it is shown that DABC performs better than two other algorithms in larger instances. (C) 2019 The Authors. Published by Elsevier Ltd.
Citation - WoS: 3
Citation - Scopus: 6
A General Variable Neighborhood Search for the NoIdle Flowshop Scheduling Problem with Makespan Criterion
(Institute of Electrical and Electronics Engineers Inc., 2019) Liangshan Shen; M. Fatih Tasgetiren; Hande Oztop; Levent Kandiller; Liang Gao; Shen, Liangshan; Tasgetiren, Mehmet Fatih; Gao, Liang; Oztop, Hande; Kandiller, Levent
This paper proposes a novel general variable neighborhood search (GVNS) algorithm to solve the no-idle flowshop scheduling problem with the makespan criterion. The initial solution of the GVNS is generated using the FRB5 heuristic. In the outer loop insert and swap operations are employed to shake the permutation. In the inner loop of variable neighborhood descent procedure two effective algorithms namely Iterated Greedy (IG) and Variable Block Insertion Heuristic (VBIH) algorithms are used. Note that an effective referenced insertion scheme is employed in these IG and VBIH algorithms. The proposed GVNS algorithm is compared with the standard IG algorithm using the benchmark instances. The computational experiments show that the GVNS performs much better than the standard IG. Furthermore the results of the standard IG and GVNS algorithms are compared with the current best-known solutions reported in the literature. The computational results show that the proposed GVNS algorithm improves some of the current best-known solutions in the literature. Consequently it can be said that the GVNS is very effective for the no-idle flowshop scheduling problem with the makespan criterion. © 2020 Elsevier B.V. All rights reserved.
Citation - WoS: 5
Citation - Scopus: 7
A Memetic Algorithm for the Bi-Objective Quadratic Assignment Problem
(ELSEVIER SCIENCE BV, 2019) Cemre Cubukcuoglu; M. Fatih Tasgetiren; I. Sevil Sariyildiz; Liang Gao; Murat Kucukvar; Tasgetiren, M. Fatih; Kucukvar, Murat; Sariyildiz, I. Sevil; Fatih Tasgetiren, M.; Cubukcuoglu, Cemre; Sevil Sariyildiz, I.; Gao, Liang; CH Dagli; GA Suer
Recently multi-objective evolutionary algorithms (MOEAs) have been extensively used to solve multi-objective optimization problems (MOPs) since they have the ability to approximate a set of non-dominated solutions in reasonable CPU times. In this paper we consider the bi-objective quadratic assignment problem (bQAP) which is a variant of the classical QAP which has been extensively investigated to solve several real-life problems. The bQAP can be defined as having many input flows with the same distances between the facilities causing multiple cost functions that must be optimized simultaneously. In this study we propose a memetic algorithm with effective local search and mutation operators to solve the bQAP. Local search is based on swap neighborhood structure whereas the mutation operator is based on ruin and recreate procedure. The experimental results show that our bi-objective memetic algorithm (BOMA) substantially outperforms all the island-based variants of the PASMOQAP algorithm proposed very recently in the literature. (C) 2019 The Authors. Published by Elsevier Ltd.
Citation - WoS: 20
Citation - Scopus: 25
A variable block insertion heuristic for solving permutation flow shop scheduling problem with makespan criterion
(MDPI AG indexing@mdpi.com Postfach Basel CH-4005, 2019) Damla Kizilay; M. Fatih Tasgetiren; Quanke Pan; Liang Gao; Kizilay, Damla; Tasgetiren, Mehmet Fatih; Gao, Liang; Pan, Quan-Ke
In this paper we propose a variable block insertion heuristic (VBIH) algorithm to solve the permutation flow shop scheduling problem (PFSP). The VBIH algorithm removes a block of jobs from the current solution. It applies an insertion local search to the partial solution. Then it inserts the block into all possible positions in the partial solution sequentially. It chooses the best one amongst those solutions from block insertion moves. Finally again an insertion local search is applied to the complete solution. If the new solution obtained is better than the current solution it replaces the current solution with the new one. As long as it improves it retains the same block size. Otherwise the block size is incremented by one and a simulated annealing-based acceptance criterion is employed to accept the new solution in order to escape from local minima. This process is repeated until the block size reaches its maximum size. To verify the computational results mixed integer programming (MIP) and constraint programming (CP) models are developed and solved using very recent small VRF benchmark suite. Optimal solutions are found for 108 out of 240 instances. Extensive computational results on the VRF large benchmark suite show that the proposed algorithm outperforms two variants of the iterated greedy algorithm. 236 out of 240 instances of large VRF benchmark suite are further improved for the first time in this paper. Ultimately we run Taillard's benchmark suite and compare the algorithms. In addition to the above three instances of Taillard's benchmark suite are also further improved for the first time in this paper since 1993. © 2019 Elsevier B.V. All rights reserved.
Citation - WoS: 12
Citation - Scopus: 14
A Variable Iterated Local Search Algorithm for Energy-Efficient No-idle Flowshop Scheduling Problem
(Elsevier B.V., 2019) M. Fatih Tasgetiren; Hande Oztop; Liang Gao; Quanke Pan; Xinyu Li; Tasgetiren, M. Fatih; Gao, Liang; Li, Xinyu; Fatih Tasgetiren, M.; Oztop, Hande; Pan, Quan-Ke; C.H. Dagli , G.A. Suer
No-idle permutation flowshop scheduling problem (NIPFSP) is a well-known NP-hard problem in which each machine must perform the jobs consecutively without any idle time. Even though various algorithms have been proposed for this problem energy efficiency has not been considered in these studies. In this paper we consider a bi-objective energy-efficient NIPFSP (EE-NIPFSP) with the objectives of makespan and total energy consumption. In the studied EE-NIPFSP we employ a speed scaling approach in which there are various speed levels for the jobs. We propose a novel mixed-integer linear programming model for the problem and we obtain Pareto-optimal solution sets for small instances using the augmented ε-constraint method. As the studied problem is NP-hard three metaheuristic algorithms are also proposed namely a multi-objective variable iterated local search (MOVILS) algorithm a multi-objective genetic algorithm (MOGA) and a MOGA with local search (MOGA-LS) for the problem. Then the performance of the proposed algorithms is assessed on both small and large instances in terms of various quality measures. The results show that the proposed algorithms are very effective for the EE-NIPFSP in terms of solution quality. Especially MOVILS and MOGA-LS algorithms are more efficient to solve large instances when compared to the MOGA. © 2020 Elsevier B.V. All rights reserved.
Citation - WoS: 57
Citation - Scopus: 67
An Adaptive Iterated Greedy algorithm for distributed mixed no-idle permutation flowshop scheduling problems
(Elsevier B.V., 2021) Yuanzhen Li; Quanke Pan; Junqing Li; Liang Gao; M. Fatih Tasgetiren; Li, Jun-Qing; Tasgetiren, M Fatih; Li, Yuan-Zhen; Gao, Liang; Pan, Quan-Ke
Distributed flow shop scheduling is a very interesting research topic. This paper studies the distributed permutation flow shop scheduling problem with mixed no-idle constraints which have important applications in practice. The optimization goal is to minimize total flowtime. A mixed-integer linear programming model is presented and an Adaptive Iterated Greedy (AIG) algorithm with the sample length changing according to the search process is designed. A restart strategy is also introduced to escape from local optima. Additionally to further improve the performance of the algorithm swap-based local search methods and acceleration algorithms for swap neighborhoods are proposed. Referenced Local Search (RLS) which shows better performance in solving scheduling problems is also used in our algorithm. In the destruction stage the job to be removed is selected according to the degree of influence on the total flowtime. In the initialization and construction phase when a job is inserted the jobs before and after the insertion position are removed and re-inserted into a better position to improve the algorithm search performance. A detailed design experiment is carried out to determine the best parameter configuration. Finally large-scale experiments show that the proposed AIG algorithm is the best-performing one among all the algorithms in comparison. © 2021 Elsevier B.V. All rights reserved.
Citation - WoS: 43
Citation - Scopus: 53
An energy-efficient bi-objective no-wait permutation flowshop scheduling problem to minimize total tardiness and total energy consumption
(PERGAMON-ELSEVIER SCIENCE LTD, 2020) Damla Yuksel; M. Fatih Tasgetiren; Levent Kandiller; Liang Gao; Yüksel, Damla; Taşgetiren, M. Fatih; Gao, Liang; Kandiller, Levent
In manufacturing scheduling sustainability concerns that raise from the service-oriented performance criteria have seldom been studied in the literature. This study aims to fill this gap in the literature by integrating the different energy consumption levels at the operational level. Since energy-efficient scheduling ideas have recently been increasing its popularity in industry due to the need for sustainable production this study will be a good resource for future energy-efficient scheduling problems. Energy consumption in high volume manufacturing is a significant cost item in most industries. Potential energy saving mechanisms are needed to be integrated into manufacturing facilities for cost minimization at the operational level. A leading energy-saving mechanism in manufacturing is to be able to adapt/change the machine speed levels which exactly determines the energy consumption of the machines. Hence in this study the afore-mentioned framework is applied to the no-wait permutation flowshop scheduling problem (NWPFSP) which is a variant of classical permutation flowshop scheduling problems. However it has various critical applications in industries such as chemical pharmaceutical food-processing etc. This study proposes both mixed-integer linear programming (MILP) and constraint programming (CP) model formulations for the energy-efficient bi-objective no-wait permutation flowshop scheduling problems (NWPFSPs) considering the total tardiness and the total energy consumption minimization simultaneously. This problem treats total energy consumption as a second objective. Thus the trade-off between the total tardiness - a service level measurement indicator - and the total energy consumption - a sustainability level indicator - is analyzed in this study. Furthermore due to the NP-hardness nature of the first objective of the problem a novel multi-objective discrete artificial bee colony algorithm (MO-DABC) a traditional multi-objective genetic algorithm (MO-GA) and a variant of multi-objective genetic algorithm with a local search (MO-GALS) are proposed for the bi-objective no-wait permutation flowshop scheduling problem. Besides the proposed algorithms are compared with the multi-objective energy-efficient algorithms from the literature. Consequently a comprehensive comparative metaheuristic analysis is carried out. The computational results indicate that the proposed MO-DABC algorithm outperforms MILP CP MO-GA MO-GALS and algorithms from the literature in terms of both cardinality and quality of the solutions. The powerful results of this study show that the proposed models and algorithms can be adapted to other energy-efficient scheduling problems such as no-idle flowshop blocking flowshop and job-shop scheduling problems or to other higher-level integrated manufacturing problems.
Citation - WoS: 31
Citation - Scopus: 33
An evolution strategy approach for the distributed blocking flowshop scheduling problem
(Elsevier Ltd, 2022) Korhan Karabulut; Damla Kizilay; M. Fatih Tasgetiren; Liang Gao; Levent Kandiller; Kizilay, Damla; Tasgetiren, M. Fatih; Gao, Liang; Karabulut, Korhan; Kandiller, Levent
Scheduling in distributed production environments has become common in recent years since the advantages of multi factory manufacturing have been growing. This paper examines the distributed blocking flowshop scheduling problem (DBFSP) to minimize the makespan. Two different mathematical models namely a mixed-integer programming model and a constraint programming model were proposed to solve the considered problem to optimality. Due to the NP-Hard nature of the problem large-size instances cannot be solved by the mathematical models and an evolutionary algorithm was proposed. Three different NEH-based heuristics were used and the first three solutions are included in the initial population whereas the rest is constructed randomly. The offspring population is generated by the self-adaptive destruction and construction (DC) procedure of the iterated greedy algorithm. Self-adaptive DC procedure is achieved by the evolution strategy approach. In the local search part of the algorithm a variable local search with three neighborhood structures was applied to the solution obtained by the DC procedure. The developed mathematical models initially verified the performance of the metaheuristic algorithm by using small instances. Then the proposed algorithm was tested on the benchmark suite from the literature. The computational results indicate that the proposed algorithm outperforms the other metaheuristic algorithms from the literature. Finally the solutions of the 156 best so far were obtained by the proposed algorithm which is more effective than the existing state-of-the-art methods. © 2021 Elsevier B.V. All rights reserved.
Citation - WoS: 33
Citation - Scopus: 37
Ensemble of metaheuristics for energy-efficient hybrid flowshops: Makespan versus total energy consumption
(Elsevier B.V., 2020) Hande Oztop; M. Fatih Tasgetiren; Levent Kandiller; D. T. Eliiyi; Liang Gao; Tasgetiren, M. Fatih; Gao, Liang; Öztop, Hande; Kandiller, Levent; Eliiyi, Deniz Türsel
Due to its practical relevance the hybrid flowshop scheduling problem (HFSP) has been widely studied in the literature with the objectives related to production efficiency. However studies regarding energy consumption and environmental effects have rather been limited. This paper addresses the trade-off between makespan and total energy consumption in hybrid flowshops where machines can operate at varying speed levels. A bi-objective mixed-integer linear programming (MILP) model and a bi-objective constraint programming (CP) model are proposed for the problem employing speed scaling. Since the objectives of minimizing makespan and total energy consumption are conflicting with each other the augmented epsilon (ε)-constraint approach is used for obtaining the Pareto-optimal solutions. While close approximations for the Pareto-optimal frontier are obtained for small-sized instances sets of non-dominated solutions are obtained for large instances by solving the MILP and CP models under a time limit. As the problem is NP-hard two variants of the iterated greedy algorithm a variable block insertion heuristic and four variants of ensemble of metaheuristic algorithms are also proposed as well as a novel constructive heuristic. The performances of the proposed seven bi-objective metaheuristics are compared with each other as well as the MILP and CP solutions on a set of well-known HFSP benchmarks in terms of cardinality closeness and diversity of the solutions. Initially the performances of the algorithms are tested on small-sized instances with respect to the Pareto-optimal solutions. Then it is shown that the proposed algorithms are very effective for solving large instances in terms of both solution quality and CPU time. © 2020 Elsevier B.V. All rights reserved.