Efficient parallel B&B method for the Blocking Job Shop Scheduling Problem

dc.contributor.authorDabah, Adel
dc.contributor.authorBendjoudi, Ahcène
dc.contributor.authorAit Zai, Abdelhakim
dc.description.abstractThe blocking job shop scheduling problem (BJSS) is a version of the classical job shop scheduling with no intermediate buffer between machines. It is known to be NP-hard in the strong sense. The major drawbacks of the previous works are the huge time needed to explore the search space and the low ratio of feasible to explored solutions when applying metaheuristics, leading to a poor quality of final solutions. In order to accelerate the exploration of the search space and overcome the drawback of metaheuristics, we propose in this paper a parallel Branch and Bound (B&B) algorithm to act both as an exact or approximate methods. The proposed parallel B&B approach is based on the master-worker paradigm, exploiting the computing power offered by cluster architectures. The master performs a breadth-first exploration to ensure high availability of tasks (sub-problems) while the workers perform a depth-first exploration in order to browse a large number of feasible solutions, therefore, obtaining a faster improvement of the solution quality. The proposed approach has been executed on a cluster based architecture using 32 nodes with 16 CPU cores each. The obtained results show a good speedup of the execution time with 80% efficiency. We have been able to solve optimally ten BJSS benchmark instances never solved before. Moreover, our proposed approach improved the best solutions for more than 22 benchmark instances.fr_FR
dc.relation.ispartofseries14th International Conference on High Performance Computing & Simulation (HPCS 2016);
dc.relation.placeInnsbruck, Austriafr_FR
dc.structureCalcul pervasif et mobile (Pervasive and Mobile Computing group)fr_FR
dc.subjectJob Shop blocking with swapfr_FR
dc.subjectParallel computingfr_FR
dc.subjectMulti-core CPUfr_FR
dc.titleEfficient parallel B&B method for the Blocking Job Shop Scheduling Problemfr_FR
dc.typeConference paper