Optimal algorithm for a two-machine flowshop scheduling problem with release dates and blocking constraints

ABSTRACT

This work focuses on the scheduling of a set of jobs with different release dates in a two-machine flowshop, where the blocking constraint is considered to minimize the sum of completion times. First, we provide the assignment and positional variable formulation for the problem under consideration and some mathematical models for particular cases of our problem. Subsequently, we derive four lower bounds based on linear relaxations. According to our formulations, we solve the studied problem exactly to provide optimal solutions. Computational experiments performed on large classes of instances show the effectiveness of the developed approaches.

KEYWORDS:

• Lower bounds
• flowshop scheduling
• exact method
• blocking constraint

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.

Disclosure statement

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

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

$x_{jk}$ binary variable

$C_{1k}$ the completion time of the job in position $k$ on machine $M_1$

$C_j$completion time of job $j$

$Time$ average CPU time (s)

$GAP$ gap

$AVG$ average of the related indicator.

$ADIS$ average relative distance

Additional information

Funding

This work was supported by the Majmaah University [RGP-2019-13].