An energy-efficient permutation flowshop scheduling problem

Abstract

Bu çalışmada, iki amaçlı bir permütasyon akış tipi çizelgeleme problemi (PATÇP) ele alınmış ve bu iki amaç arasındaki değişimin görülebilmesi için toplam enerji tüketimini ve maksimum tamamlanma zamanını en aza indirecek hedefler için iki amaçlı karışık tamsayılı doğrusal programlama modeli önerilmiştir. Literatürde çok sayıda çok amaçlı PATÇP'nin sunulmasına rağmen, bu problemin enerji tüketimi açısından değerlendirilmesi çok nadirdir. Enerji-etkin akış tipi çizelgeleme probleminde, küçük boyutlu problemler üretilmiştir ve Pareto optimal çözüm setlerini üretmek için epsilon kısıtlama yöntemi (AUGMECON) kullanılmıştır. Daha büyük boyutlu problemler için ise, CPLEX üzerinde belirlenmiş zaman sınırı ile epsilon-kısıtlama yöntemi kullanılarak Pareto çözüm setlerine yaklaşılmıştır. Çözüm yöntemi olarak, Iteratif açgözlü algoritması (IGALL) ve değişken blok yerleştirme (VBIH) algoritması kullanılmıştır. IGALL ve VBIH algoritmalarının performansları ilk olarak küçük boyutlu, daha sonra, büyük boyutlu problemler üzerinde denenmiştir. IGALL ve VBIH algoritması küçük boyutlu problemleri kolayca çözebilmektedir. Bu iki algoritmanın, büyük boyutlu problemleri çözmek için, zaman-sınırlı CPLEX ile karşılaştırıldığında son derece etkili olduğu gösterilmiştir.

In this thesis, to solve permutation flowshop scheduling problem (PFSP), a bi-objective mixed integer linear programming model with the objectives of minimizing the total energy consumption (TEC) and makespan is proposed in order to see the trade-off between them. Heuristic algorithms; iterated greedy (IGALL) algorithm, which is recently adapted in literature, and variable block insertion heuristic (VBIH) are presented. To test the performance of the algorithms, extensive experimental evaluations are carried out on the well-known benchmark suite of Taillard (Taillard, 1993).Permutation flowshop scheduling problem is a well-known problem in the literature. The permutation flowshop represents a particular case of the flowshop-scheduling problem, having as a goal of an optimal schedule out of the n! possible sequences for n jobs on m machines on which these n jobs are to be processed. Thus, it is classified as a complex combinatorial optimization problem. Energy consumption consideration in the role of scheduling can be very seldom seen in the literature, even though many service-oriented scheduling articles and studies for PFSP have been adapted. Mostly, maximum completion time is considered as an only criterion. There is a considerable gap between makespan and energy consumption criteria. An effective way to improve energy efficiency in a production plant should address to design scheduling strategies, which aims to reduce the energy consumption of the process. Since there is a multi-objective decision model in this thesis, there is no single optimal solution, which simultaneously optimizes all the objectives. The effort of this thesis is to effectively implement the constraint method for generating the Pareto optimal solutions and the aim of the thesis is to show the trade-off between minimizing makespan and total energy consumption while providing a managerial sense where energy saving may result in reduced service level and vice versa.The augmented-epsilon constraint method is employed for generating the Pareto optimal solution sets for small-sized instances. For larger instances, the augmented epsilon-constraint method with a time limit is used on CPLEX for approximating the Pareto solution sets. As the heuristic methods, a very recent iterated greedy algorithm (IGALL) and an energy-efficient variable block insertion heuristic (VBIH) algorithm are proposed with employing the speed scaling strategy similar to those proposed in (Ding et al., 2016) and (Mansorui et al., 2016) from the literature. First, the performance of VBIH and IGALL algorithms on small sized problems are given, then, it is shown that the VBIH and IGALL algorithms are extremely effective for solving larger instances when compared to the time-limited CPLEX.