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.
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
set of jobs
number of jobs
Machine 1
Machine 2
release date
processing time on machine 1
processing time on machine 2
binary variable
the completion time of the job in position on machine
completion time of job
average CPU time (s)
gap
average of the related indicator.
average relative distance