A TWO-STAGE GREEDY HEURISTIC FOR A FLOWSHOP SCHEDULING PROBLEM UNDER TIME-OF-USE ELECTRICITY TARIFFS

Abstract

This paper studies a two-machine flowshop scheduling problem under time-dependent electricity tariffs, in which electricity prices may vary from time to time throughout the day. The main issue is to assign a set of jobs to available time slots with different electricity prices to minimise the total resource cost required for processing the jobs. The main contribution of this work is two-fold. First, a new continuous-time mixed-integer linear programming (MILP) model is proposed for the problem. Second, a two-stage greedy heuristic is developed. A computational experiment on randomly generated instances demonstrates that the greedy algorithm can improve the objective function by almost 40 percent. The algorithm can be applied by production managers to scheduling jobs in a flowshop under time-of-use (TOU) electricity tariffs to save electricity costs.

Keywords

• Scheduling
• mathematical modeling
• heuristic algorithm
• energy