Energy Consideration in Parallel Machine Scheduling

Motivation

Recent sustainable development efforts have surfaced concerns about energy usage. Rapid economic growth leading to high energy demand is considered one of the most significant driving forces toward environmental degradation. The industrial sector is a major electricity consumer, and by using energy-efficient planning and scheduling, one can significantly reduce environmental impact without the need to invest in more efficient equipment. The production sectors incur a considerable energy cost, and reducing it can lead to both cost savings and environmental benefits.

Scheduling is a decision-making process concerned with allocating finite resources to jobs with the objective of minimizing some (single or multiple) performance measures. In a production environment, scheduling helps assign the raw materials, resources, or processes to various jobs or products. Most conventional scheduling problems have considered traditional objectives like makespan, total completion time, and other tardiness-related objectives. Incorporating energy-related objectives in the scheduling problems will result in a more sustainable and environmentally friendly schedule.

The scheduling literature contains different forms of energy considerations in the objective or as constraints. These include the minimization of energy consumption, carbon emission, energy cost with fixed or time-varying tariffs, and peak power. It has been noticed that there are limited studies considering multi-objective scheduling problems in parallel machines with energy costs under a Time-of-Use (ToU) tariff policy. Thus, we focus our study to parallel machine scheduling problem with one objective being the minimization of energy cost with ToU tariff.  

Problem Definition

For the following three bi-objectives problems, we aim to provide an efficient solution method and also to investigate various factors or model parameters that affect the resulting schedule.

The problem of scheduling jobs on unrelated parallel machines to minimize energy cost (under the Time-of-Use tariff policy) and a traditional scheduling objective in a deterministic environment is considered. The energy cost consists of both the demand charges as well as the consumption charges, as the demand charges are considerably higher than the consumption charges. The other objectives for the first, second, and third problems are minimizing the total weighted completion time, load imbalance among the machines, and total weighted number of tardy jobs. 

In the considered problems, each machine is allowed to switch states during the schedule. Various machine states include processing, idle, turning-off, off, and turning-on states, each having different power requirements, which would help exploit the low off-peak prices to process the jobs. Additionally, adjusting each machine's processing speed can alter the processing-power consumption. This is known as the speed scaling strategy, which significantly reduces the total energy consumption with some sacrifice to the completion time of the jobs.

Thus, studying the trade-off between traditional scheduling objectives and the energy cost brings us closer to real-world problems. Moreover, including demand charges in energy cost calculation results in a schedule with lower demand fluctuations, sparing electricity utility companies from investing in expensive peaker generators.