Heuristic solutions to minimise makespan in a hybrid flow shop scheduling environment with energy consumption constraints in steel making

Abstract

Due to its advantage over other alternative energy efficient methods in cost savings, there has been an increasing interest in applying energy efficient scheduling in energy intensive industries faced with a conundrum of optimising production while consum ing less energy. In this dissertation, the energy-efficient hybrid flow shop scheduling problem is addressed to minimise the makespan without violating the total energy consumption threshold and where the threshold is not violated. None of the authors that apply the speed scaling mechanism under uniform parallel machines in the EHFSP domain consider each machine’s rate of response to a change in processing speed, the attack time. Therefore, the main contribution of this dissertation lies in addressing this gap,the consideration of attack time during speed scaling. The proposed algorithms seek to find the best makespan that incurs the minimum energy consumption where such alternative may exist. Energy is set as a constraint in re sponse to the dilemma faced by energy-intensive industries to continue fostering and sustaining competitive production by using less energy under an energy constraint. To solve the problem, two algorithms were proposed, each of which is an integration of some other scheduling heuristics, meta- and hyper-heuristics. The first is called the Improved Hyper heuristic NEH (IHNEH) algorithm, while the second is called the Improved Hyper heuristic GA (IHGA) algorithm. Each of the two algorithms operate in three stages, and share the first step, which is where the hyper heuristic is used to select a low-level heuristic for implementation in both solutions. The second step is what distinguishes the two solution. For the IHNEH algorithm, the NEH algorithm is used as the job sequencing procedure, while the IHGA makes use of the GA procedure. It was found that even though both algorithms were improved using the same improvement method, the IHNEH still displayed a superior performance over the IHGA especially for medium to large size problems in terms of the makespan and the energy consumption. The poor performance of the IHGA might be due to the random generation of the initial job sequence instead of using a constructive heuristic. The goodness of heuristic was used to measure the effectiveness of the two methods, and the computational results indicate that the methods were able to produce makespan values that deviate from the actual makespan by at most 2% for small size jobs. In terms of energy consumption, the IHNEH was able to produce energy consumption values that deviate from the actual energy consumption by 0% for small size jobs. For medium and large size jobs, the IHNEH had a deviation from the best makespan and energy consumption of 0, outperforming both the IHGA and the Branch and Bound under the time bound imposed. This implies that the IHNEH is a good technique for this problem given the energy threshold applied. Future studies can change that and study their influence on the Cmax and the energy consumption. Future work can also focus on extending the energy threshold further and study how many jobs can be processed without violating the threshold. The attack time values of machines were not based on actual industry data, however, future work could focus on obtaining these values to obtain more practical results. Also, speed scaling was not applied using actual machine speeds, but rather using speed factors, therefore future work could consider using actual speeds of machines. There are other alternative meta-heuristics that were not considered such as the PSO, and SA which are also capable of producing good results, and therefore they can also be used. Another suggestion for future research is initialising the GA with non random chromosomes to improve its performance. The performance of the GA is not only dependent on the quality of the initial solution and the termination criteria whose sensitivity analysis was presented, there are other factors that influence the GA such as the size of the population, the mutation and the crossover rate, therefore, it would be interesting to perform a sensitivity analysis of these parameters for future work.