167. Minimizing Energy Consumption and Makespan for Unrelated Parallel Machines with Speed Scaling
Invited abstract in session WD-12: Practical problems in scheduling , stream Scheduling and Project Management.
Wednesday, 14:30-16:00Room: Clarendon SR 1.02
Authors (first author is the speaker)
| 1. | Shubham Keshri
|
| Department of Management Sciences, Indian Institute of Technology Kanpur | |
| 2. | Avijit Khanra
|
| Department of Management Sciences, Indian Institute of Technology Kanpur |
Abstract
We consider an unrelated parallel scheduling problem with release dates, setup time, and machine eligibility restrictions to minimize the makespan and the sum of processing, setup, and idle energy consumption. Discrete speed scaling is allowed, assuming that higher processing speed leads to higher processing power. Thus, the two objectives are in conflict. The epsilon-constrained method is employed to a reformulated problem of energy minimization with a bounded makespan. This problem is then decomposed into an assignment problem and single-machine scheduling problems. A Variable Neighborhood Descent (VND) algorithm is used to obtain the assignment, determining the processing energy, while the setup and idle energy are obtained using the earliest release date rule. The neighborhoods considered include shift, swap, and long chain neighborhoods. To handle the makespan constraint, weighted penalty terms are introduced into the objective function. This enables the VND algorithm to explore infeasible regions by adjusting these weights. A mixed-integer linear programming model is formulated and CPLEX solver is used to construct the approximate Pareto front, which serves as a benchmark. Results reveal the proposed VND algorithm produces high-quality, non-dominated fronts in a reasonable amount of time. Future work can consider energy cost with a time-of-use tariff, enhancing the applicability of the problem and supporting sustainable scheduling in energy intensive industries.
Keywords
- Scheduling
- Multi-Objective Decision Making
- Metaheuristics
Status: accepted
Back to the list of papers