Parallel-machine scheduling to minimize tardiness penalty and power cost

被引:117
作者
Fang, Kuei-Tang [1 ]
Lin, Bertrand M. T. [1 ]
机构
[1] Natl Chiao Tung Univ, Dept Informat & Finance Management, Inst Informat Management, Hsinchu 300, Taiwan
关键词
Parallel-machine scheduling; Total weighted tardiness; Dynamic voltage scaling; Particle swarm optimization; SWARM OPTIMIZATION ALGORITHM;
D O I
10.1016/j.cie.2012.10.002
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
Traditional research on machine scheduling focuses on job allocation and sequencing to optimize certain objective functions that are defined in terms of job completion times. With regard to environmental concerns, energy consumption becomes another critical issue in high-performance systems. This paper addresses a scheduling problem in a multiple-machine system where the computing speeds of the machines are allowed to be adjusted during the course of execution. The CPU adjustment capability enables the flexibility for minimizing electricity cost from the energy saving aspect by sacrificing job completion times. The decision of the studied problem is to dispatch the jobs to the machines as well as to determine the job sequence and processing speed of each machine with the objective function comprising of the total weighted job tardiness and the power cost. We give a formal formulation, propose two heuristic algorithms, and develop a particle swarm optimization (PSO) algorithm to effectively tackle the problem. Since the existing solution representations do not befittingly encode the decisions involved in the studied problem into the PSO algorithm, we design a tailored encoding scheme which can embed all decisional information in a particle. A computational study is conducted to investigate the performances of the proposed heuristics and the PSO algorithm. (C) 2012 Elsevier Ltd. All rights reserved.
引用
收藏
页码:224 / 234
页数:11
相关论文
共 29 条
[1]   Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem [J].
Ai, The Jin ;
Kachitvichyanukul, Voratas .
COMPUTERS & INDUSTRIAL ENGINEERING, 2009, 56 (01) :380-387
[2]   Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach [J].
Anghinolfi, Davide ;
Paolucci, Massimo .
COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (11) :3471-3490
[3]  
[Anonymous], P IEEE FIFC
[4]  
Baker K. R., 1974, Introduction to Sequencing and Scheduling"
[5]   Power-aware scheduling for makespan and flow [J].
Bunde, David P. .
JOURNAL OF SCHEDULING, 2009, 12 (05) :489-500
[6]   MINMAX EARLINESS TARDINESS SCHEDULING IN IDENTICAL PARALLEL MACHINE SYSTEM USING GENETIC ALGORITHMS [J].
CHENG, RW ;
GEN, MS ;
TOZAWA, T .
COMPUTERS & INDUSTRIAL ENGINEERING, 1995, 29 :513-517
[7]   MINIMIZING TOTAL TARDINESS ON ONE MACHINE IS NP-HARD [J].
DU, JZ ;
LEUNG, JYT .
MATHEMATICS OF OPERATIONS RESEARCH, 1990, 15 (03) :483-495
[8]   A particle swarm optimization for solving joint pricing and lot-sizing problem with fluctuating demand and trade credit financing [J].
Dye, Chung-Yuan ;
Ouyang, Liang-Yuh .
COMPUTERS & INDUSTRIAL ENGINEERING, 2011, 60 (01) :127-137
[9]   STRONG NP-COMPLETENESS RESULTS - MOTIVATION, EXAMPLES, AND IMPLICATIONS [J].
GAREY, MR ;
JOHNSON, DS .
JOURNAL OF THE ACM, 1978, 25 (03) :499-508
[10]  
Ge R., 2005, P ACMIEEE SC C SUPER, P34