Diz 74 en
Scheduling under energy consumption limits
Author: István Módos
With the increasing costs for energy consumption of large manufacturing companies, the newest trend of energy-efficient and sustainable scheduling appeared within the scientific literature. To design an automated scheduling system for such companies, it not sufficient anymore to consider only traditional objectives such as makespan. The production schedules must also take the energy-related aspects into account. Otherwise, such schedules are not usable in practice, or they would require many hand-made changes by human schedulers. One of such aspects addressed by this work is the energy consumption limit, representing an upper limit of the energy consumption within every metering interval of a day. The energy consumption limits are specified in a contract between a manufacturing company and an electric utility, and its violation is monetarily penalized. The motivational example for this research is a company producing tempered glass, which violated the energy consumption limits a few times per month. Usually, the violation was caused due to uncertainty in the preparation time of the jobs. In such a situation, energy-demanding jobs were executed within the same metering interval; thus, the energy consumption increased, and the energy limit was violated. This thesis investigates the scheduling problem with the energy limits, which is considered in both deterministic and stochastic environments. In the deterministic environment, it is expected that the start times of the jobs are never delayed; this problem has its application in fully automated production or in companies, which strictly penalize its workers for such delays. We studied the computation complexity of different problem variants: the main result is that the problem with fixed ordering of the jobs, constant number of machines, and assumption that the jobs cannot cross multiple metering intervals can be solved in polynomial time. The study of the problem within a stochastic environment focuses on the robustness of the production schedules, i.e., how to obtain schedules that do not violate the energy consumption limits even in case of unexpected disturbances. Due to the complex nature of such a problem, only a single machine problem is investigated. However, we discovered that if the order of the jobs is fixed, such a problem can be solved in a pseudo-polynomial time; the developed algorithm is then utilized in exact and heuristic algorithms. For both deterministic and stochastic environments, we proposed exact (optimization models, Branch-and-Bound, Logic-based Benders decomposition) and heuristic (adaptive local search) algorithms so that large instances with hundreds of jobs can be solved. The proposed methods were compared with with the adapted ones from the literature, which we improved and outperformed in the number of better solutions found.