Multi-Objective Green Hybrid Flowshop Scheduling Problems

Abstract

Literatürde, hibrid akış tipi çizelgeleme problemi çeşitli üretim verimliliği bazlı amaç fonksiyonları düşünülerek yaygın bir şekilde çalışılmıştır. Ancak, hibrid akış tipi çizelgeleme problemi için enerji tüketimi ve çevresel etkileri dikkate alan çalışmalar literatürde oldukça azdır. Bu tez, makinelerin değişen hız seviyelerinde çalışabildiği hibrid akış tipi atölyelerindeki, maksimum tamamlanma zamanı ve toplam enerji tüketimi amaç fonksiyonları arasındaki çelişkiyi ele almaktadır. Bu tezde, enerji-verimli hibrid akış tipi çizelgeleme problemi için, hız ölçeklendirme yöntemi kullanılarak, özgün iki-amaçlı karma-tamsayılı doğrusal programlama ve iki-amaçlı kısıt programlama model formülasyonları önerilmiştir. Bu tezde, hız ölçeklendirme yönteminin hem iş-bazlı hem de iş-tezgah (matris)-bazlı versiyonları çalışılmıştır. Maksimum tamamlanma zamanını ve toplam enerji tüketimini minimize etme amaç fonksiyonları birbirleriyle çeliştiklerinden dolayı, Pareto-optimal çözümleri elde etmek için genişletilmiş epsilon kısıt yöntemi kullanılmıştır. Küçük örnekler için Pareto-optimal eğriye oldukça yakın yaklaşımlar elde edilirken, büyük örnekler için ise önerilen karma-tamsayılı doğrusal programlama ve kısıt programlama model formülasyonları belirli bir süre limiti altında çözülerek baskın olmayan çözüm kümeleri elde edilmiştir. Ayrıca, çalışılan problemin NP-zor sınıfına ait bir problem olmasından dolayı, enerji-verimli hibrid akış tipi çizelgeleme probleminin hem iş-bazlı hem de matris-bazlı versiyonları için özgün iki-amaçlı metasezgisel algoritmalar özgün bir yapıcı sezgisel ile birlikte önerilmiştir. Problemin iş-bazlı versiyonu için iki tip yinelemeli açgözlü algoritma, bir değişken blok yerleştirme sezgiseli ve dört tip bütünleşik-metasezgisel algoritmalar önerilmiştir. Ayrıca, problemin matris-bazlı versiyonu için iki tip yinelemeli açgözlü algoritma, bir değişken blok yerleştirme sezgiseli ve bir bütünleşik-metasezgisel algoritma önerilmiştir. Bunların yanı sıra, bu tez, hibrid akış tipi çizelgeleme problemi için iki özgün sezgisel amaç fonksiyonu değeri hesaplama yöntemi de önermektedir. Literatürde oldukça bilinen hibrid akış tipi çizelgeleme problemi örnekleri kullanılarak, önerilen iki-amaçlı metasezgisellerin performansları birbirleriyle ve karma-tamsayılı doğrusal programlama ve kısıt programlama model formülasyonlarının çözümleri ile; çözümlerin sayısallığı, çeşitliliği ve yakınlığı açılarından kıyaslanmıştır. Öncelikle, metasezgisellerin performansı küçük örnekler üzerinde Pareto-optimal çözümler ile kıyaslanarak test edilmiştir. Ardından, önerilen metasezgisellerin büyük örnekleri çözmek adına hem çözüm kalitesi hem de çözüm süresi açısından oldukça etkin olduğu gösterilmiştir.

The hybrid flowshop scheduling problem (HFSP) has been extensively studied in the literature with various production-efficiency related objectives. Nevertheless, studies that consider energy consumption and environmental impacts have rather been limited for the HFSP in the literature. This thesis addresses the trade-off between makespan and total energy consumption objectives in hybrid flowshops, where machines can operate at varying speed levels. In this thesis, new bi-objective mixed-integer linear programming (MILP) and bi-objective constraint programming (CP) models are proposed for the energy-efficient HFSP employing a speed scaling method, where both job-based and job-machine (matrix)-based versions of the speed scaling are considered. Since the objectives of minimizing makespan and total energy consumption are contradicting with each other, the augmented ε-constraint method is employed for obtaining the Pareto-optimal solutions. While close approximations for the Pareto-optimal frontier are obtained for small instances, sets of non-dominated solutions are found for large instances by solving the proposed MILP and CP models under a time-limit. Since the studied problem is NP-hard, new bi-objective metaheuristic algorithms are also proposed for both job-based and matrix-based versions of the energy-efficient HFSP as well as a constructive heuristic. Namely, two variants of the iterated greedy algorithm, a variable block insertion heuristic and four variants of an ensemble of metaheuristic algorithms are proposed for the job-based version of the problem. Furthermore, two variants of the iterated greedy algorithm, a variable block insertion heuristic and an ensemble of metaheuristic algorithms are proposed for the matrix-based version of the problem. This thesis also presents two new heuristic fitness calculation approaches for the HFSP. The performances of the proposed bi-objective metaheuristics are compared with each other as well as the MILP and CP solutions on a well-known HFSP benchmark set in terms of cardinality, diversity and closeness of the solutions. Initially, the performance of the metaheuristics is tested on small instances with regard to the Pareto-optimal solutions. Subsequently, it is shown that the proposed metaheuristics are very effective for solving large instances in terms of both solution quality and computational time.