Metaheuristic algorithms for the two-machine flowshop scheduling problem with release dates and blocking constraint

ABSTRACT

This paper reports a study of the flowshop scheduling problem with two machines where a set of tasks must be scheduled on a set of machines respecting the same fixed order. The objective was to design the best schedule optimizing the sum of completion times for the job criteria while respecting the release dates (i.e. start times) and the classical blocking constraint, whereby a job remains blocked on a machine as long as the next machine in execution is unavailable or the buffer cannot receive the job. We examine several metaheuristics based on simulated annealing, local search, discrete differential evolution, and genetic algorithms.

The experimental results compare the performance of the proposed metaheuristics with each other.

KEYWORDS:

• Flowshop scheduling
• local search
• genetic algorithm
• blocking constraint
• simulated annealing

Acknowledgments

The authors would like to thank the Deanship of Scientific Research at Majmaah University for supporting this work under Project Number No. RGP-2019-13.

Nomenclature

$J=\left\{1,\dots ,n\right\}$ set of jobs

$n$ number of jobs

$M_1$ Machine 1

$M_2$ Machine 2

$r_j$ release date

$p_{1j}$ processing time on machine 1

$p_{2j}$ processing time on machine 2

${\mathrm{C}}_{\mathrm{m}\mathrm{a}\mathrm{x}}$ the completion time: makespan

$C_j$ completion time of job $j$

$Time$ average CPU time (s)

$Gap$ gap

$ARPD$ average relative percentage deviation.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

The authors would like to thank the Deanship of Scientific Research at Majmaah University for supporting this work under Project Number No.RGP-2019-13.