Single machine parallel-batch scheduling under time-of-use electricity prices: New formulations and optimisation approaches

Zheng Tian and Li Zheng

European Journal of Operational Research, 2024, vol. 312, issue 2, 512-524

Abstract: Electricity costs account for a relatively large proportion of total production costs in many energy-intensive manufacturing industries. And energy-efficient scheduling is getting increasing attention from researchers owing to its wide real-world applications and computational challenges. In this study, the single-machine parallel-batch scheduling problem with non-identical job sizes under time-of-use electricity prices is investigated. The objective is to minimise the total energy consumption cost such that the makespan does not exceed a given deadline. First, an improved time-slot-indexed formulation is proposed to eliminate symmetric solutions. Subsequently, a new set partition-based formulation is developed. To the best of our knowledge, there is no exact algorithm for this problem, except for some formulations solved by off-the-shelf solvers. To address this problem, a branch-and-price algorithm is developed with a novel and efficient branching rule. In addition, a column-generation-based heuristic is proposed to solve larger-scale instances. Extensive numerical experiments show that the efficiency of the branch-and-price algorithm is significantly better than that of off-the-shelf solvers, and many instances with up to 100 jobs could be solved to optimality within a 20-minute computational time limit for the first time. The column-generation-based heuristic can efficiently provide better solutions than existing heuristics (2.75% average gap in three minutes on instances with 100 jobs and 3.12% average gap in ten minutes on instances with 200 jobs).

Keywords: Scheduling; Batch processing; Energy consumption cost; Column generation; Branch and price (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723005507
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:312:y:2024:i:2:p:512-524

DOI: 10.1016/j.ejor.2023.07.012

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().