Elsevier

Applied Soft Computing

Volume 84, November 2019, 105701
Applied Soft Computing

Two-stage hybrid flow shop scheduling on parallel batching machines considering a job-dependent deteriorating effect and non-identical job sizes

(Click DOI to download directly)

Highlights

The coordinated two-stage hybrid flow shop scheduling on parallel batching machines considering the job-dependent deteriorating effect and non-identical job sizes is first investigated in this paper.

For the single parallel batching problem, we first propose a three-dimensional wasted volume based on the job normal processing time, size, and deteriorating rate. A heuristic algorithm is derived to batch all the jobs to minimize the makespan.

We develop an effective hybrid EDA-DE which combines EDA and DE to solve the two-stage hybrid flow shop problem.

Abstract

In this paper, we investigate a specialized two-stage hybrid flow shop scheduling problem with parallel batching machines considering a job-dependent deteriorating effect and non-identical job sizes simultaneously. A novel concept of three-dimensional wasted volume based on the job normal processing time, job size, and job deteriorating rate is first proposed. Some structural properties, as well as a heuristic algorithm, are developed to solve the single parallel batching machine scheduling problem. Since the two-stage hybrid flow shop scheduling problem is NP-hard, a hybrid EDA-DE algorithm combining estimation of distribution algorithm (EDA) and differential evolution (DE) algorithm is proposed to tackle the studied problem. In addition, the Taguchi method of design of experiments (DOE) is implemented to tune the parameters of the EDA-DE. Finally, a series of computational experiments are carried out to compare the performance of the proposed hybrid EDA-DE algorithm and some recent existing algorithms from the literature, and the comparative results validate the effectiveness and efficiency of the proposed algorithm.

Keywords

Hybrid flow shop scheduling
Parallel batching
Job-dependent deteriorating effect
Heuristic
Hybrid EDA-DE algorithm
View full text