A simulated annealing for hybrid flow shop scheduling with multiprocessor tasks to minimize makespan

This paper studies a hybrid flow shop scheduling problem (hybrid FSSP) with multiprocessor tasks, in which a set of independent jobs with distinct processor requirements and processing times must be processed in a k -stage flow shop to minimize the makespan criterion. This problem is known to be str...

Full description

Saved in:
Bibliographic Details
Published in:International journal of advanced manufacturing technology 2011-03, Vol.53 (5-8), p.761-776
Main Authors: Wang, Hui-Mei, Chou, Fuh-Der, Wu, Ful-Chiang
Format: Article
Language:English
Subjects:
Algorithms
CAE) and Design
Computer simulation
Computer-Aided Engineering (CAD
Engineering
Heuristic methods
Industrial and Production Engineering
Job shop scheduling
Job shops
Mechanical Engineering
Media Management
Microprocessors
Multiprocessing
Original Article
Permutations
Polynomials
Production scheduling
Simulated annealing
Task scheduling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper studies a hybrid flow shop scheduling problem (hybrid FSSP) with multiprocessor tasks, in which a set of independent jobs with distinct processor requirements and processing times must be processed in a k -stage flow shop to minimize the makespan criterion. This problem is known to be strongly nondeterministic polynomial time (NP)-hard, thus providing a challenging area for meta-heuristic approaches. This paper develops a simulated annealing (SA) algorithm in which three decode methods (list scheduling, permutation scheduling, and first-fit method) are used to obtain the objective function value for the problem. Additionally, a new neighborhood mechanism is combined with the proposed SA for generating neighbor solutions. The proposed SA is tested on two benchmark problems from the literature. The results show that the proposed SA is an efficient approach in solving hybrid FSSP with multiprocessor tasks, especially for large problems.
ISSN:0268-3768
1433-3015
DOI:10.1007/s00170-010-2868-z