An efficient greedy insertion heuristic for energy-conscious single machine scheduling problem under time-of-use electricity tariffs. (15th August 2016)

• Record Type: Journal Article
• Authors: Che, Ada; Zeng, Yizeng; Lyu, Ke
• Is Part Of: Journal of cleaner production. Volume 129(2016:Aug.)
• Page Start: 565
• Page End: 577
• Publication Date: 2016-08-15
• Subjects: Single machine scheduling -- Time-of-use (TOU) tariffs -- Electricity cost -- Greedy insertion heuristic; Factory and trade waste -- Management -- Periodicals; Manufactures -- Environmental aspects -- Periodicals; Déchets industriels -- Gestion -- Périodiques; Usines -- Aspect de l'environnement -- Périodiques; 628.5
• DOI: 10.1016/j.jclepro.2016.03.150
• Languages: English
• ISSNs: 0959-6526

Abstract

Abstract: This paper addresses an energy-conscious single machine scheduling problem under time-of-use (TOU) or time-dependent electricity tariffs, in which electricity prices may vary from hour to hour throughout a day. The key issue is to assign a set of jobs to available time periods with different electricity prices so as to minimize the total electricity 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, an efficient greedy insertion heuristic is developed. In the proposed heuristic, the jobs are inserted into the available time periods one after another in non-increasing order of their electricity consumption rates and each job is inserted into the time period(s) with minimum electricity cost. A real-life case study from a Chinese company reveals that the total electricity cost can be reduced by about 30% with the proposed algorithm. Computational experiment on randomly generated instances also demonstrates that our algorithm can yield high-quality solutions with low electricity costs within dozens of seconds for large-scale single machine scheduling problems with 5000 jobs. The algorithm can be applied by production managers to scheduling jobs on a single machine under TOU electricity tariffs to save electricity costs. Highlights: Single machine scheduling problem under time-of-use (TOU) electricity tariffs is addressed. The objective is to minimize the total electricity cost within a given makespan. A continuous-time mixed-integer linear programming (MILP) model is developed. An efficient greedy insertion heuristic is proposed. The algorithm is validated by a real-life instance and randomly generated instances.