Improved mixed-integer linear programming model and heuristics for bi-objective single-machine batch scheduling with energy cost consideration

ABSTRACT

This article addresses bi-objective single-machine batch scheduling under time-of-use electricity prices to minimize the total energy cost and the makespan. The lower and upper bounds on the number of formed batches are first derived and a continuous-time mixed-integer linear programming model is proposed, which improves an existing discrete-time model in the literature. Two improved heuristics are proposed based on the improved model. Computational experiments demonstrate that the improved model and heuristics can run hundreds of times faster than the existing ones for large-size instances.

KEYWORDS:

• Single-machine batch scheduling
• time-of-use (TOU) electricity prices
• bi-objective optimization
• mixed-integer linear programming (MILP)
• heuristics

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was partially supported by the National Natural Science Foundation of China [grant numbers 71471145, 71071129].