A branch-and-bound algorithm for minimizing the energy consumption in the PFS problem

Guo Sheng Liu, Bi Xi Zhang, Hai Dong Yang, Xin Chen, George Q. Huang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

40 Citations (Scopus)

Abstract

This paper considers the energy consumption minimization in permutation flow shop (PFS) scheduling problem. The energy consumption of each machine is decomposed into two parts: useful part which completes the operation at current stage and wasted part which is consumed during idle period. The objective considered here is to minimize the total wasted energy consumption which is a weighted summation of the idle time of each machine. To solve this new problem, a branch-and-bound algorithm is developed. Two lower bounds are proposed, and an initial upper bound by using a variant of NEH heuristic algorithm is applied. Compared with the makespan minimization criterion, this model deduces more energy-saving solutions. Experimental results also validate the efficiency of the proposed algorithm for problems with job number not larger than 15.

Original languageEnglish
Article number546810
JournalMathematical Problems in Engineering
Volume2013
DOIs
Publication statusPublished - 2013
Externally publishedYes

ASJC Scopus subject areas

  • General Mathematics
  • General Engineering

Fingerprint

Dive into the research topics of 'A branch-and-bound algorithm for minimizing the energy consumption in the PFS problem'. Together they form a unique fingerprint.

Cite this