International Conference Papers
Permanent URI for this collection
Browse
Browsing International Conference Papers by Author "Ait Zai, Abdelhakim"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
- ItemEfficient parallel B&B method for the Blocking Job Shop Scheduling Problem(2016-07) Dabah, Adel; Bendjoudi, Ahcène; Ait Zai, AbdelhakimThe 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.
- ItemMulti and Many-core Parallel B&B approaches for the Blocking Job Shop Scheduling Problem(2016-07) Dabah, Adel; Bendjoudi, Ahcène; Ait Zai, Abdelhakim; El Baz, Didier; Nouali-Taboudjemat, NadiaIn this paper, we propose three approaches to accelerate the B&B execution time using Multi and Many-core systems to solve the NP-hard Blocking Job Shop Scheduling problem (BJSS). The first approach is based on Master/Worker paradigm where the workers independently explore the branches sent by the master. The second approach is a node-based parallelization that does not change the design of the B&B algorithm, except that the bounding process is faster since it is calculated in parallel using several threads organized in one GPU block. The third approach is a Multi-Core CPU/GPU hybridization that benefits from the power of both the CPU-cores and the GPU at the same time. This hybridization is based on concurrent kernels execution provided by Nvidia Multi process Service (MPS) i.e. each host process (Master or Worker) launches his own kernel to accelerate the bounding process on GPU. The obtained results using Taillard instances confirm the efficiency of our proposals. The first two approaches are respectively three and eighteen times faster compared to the sequential version. The results of the hybrid approach show a relative speedup over ninety times as compared to the sequential approach and therefore prove the advantage of using both the CPU-cores and the GPU at the same time.