Browsing by Author "Ait Zai, Abdelhakim"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Efficient parallel B&B method for the Blocking Job Shop Scheduling Problem
    (2016-07) Dabah, Adel; Bendjoudi, Ahcène; Ait Zai, Abdelhakim
    The 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.
  • Thumbnail Image
    Item
    GPU parallel B&B for the Blocking job shop scheduling problem.
    (CERIST, 2016-02-22) Dabah, Adel; Bendjoudi, Ahcène; Ait Zai, Abdelhakim; El Baz, Didier
    Branch and bound algorithms (B&B) are well known techniques for solving optimally combinatorial optimization problems. Nevertheless, these algorithms remain inefficient when dealing with large instances. This paper deals with the blocking job shop scheduling (BJSS), which is a version of classical job shop scheduling with no intermediate buffer between machines. This problem is an NP-hard problem and its exact resolution using the sequential approach is impractical. We propose in this paper a GPU-based parallelization in which a two level scheme is used. The first level is a node-based parallelization in which the bounding process is faster because it is calculated in parallel using several threads organized in one GPU block. To fully occupy the GPU, we propose a second level of parallelization which is a generalization of the first level. Therefore, for each iteration several search tree nodes are evaluated on the GPU using several thread-blocks. The obtained results, using the well-known Taillard instances, confirm the efficiency of the proposed approach. Also, the results show that our approach is 65 times faster than an optimized sequential B&B version.
  • Thumbnail Image
    Item
    Multi 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, Nadia
    In 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.