Thesis (Ph.D.) - Cairo University - Institute of Statistical Studies and Research - Department of Operation Research

In this thesis, it is Proposed a new technique of meta-heuristic techniques to solve the Job Shop Scheduling Problem(JSSP). Meta-heuristic techniques have been proven successfully to solve various NP-hard problems while the exact methods are guaranteed to find the optimal solution for small problems but they are useless for large problems. Bat Algorithm (BA) is applied as novel meta-heuristic technique to solve the JSSP. Bat Algorithm (BA) is proposed by Yang In 2010. It is based on swarm intelligence and the inspiration form observing the bats. The capability of echolocation of microbats is fascinating as these bats can find their prey and discriminate different types of insects even in complete darkness. In JSSP, there is a set of job J = {J1, J2, . . ., Jn}and a set of machine M = {M1, M2, . . .,Mm}. Each job j must be processed by m machines to complete its work. Each job includes of a set of operations. The sequence of the operations of each job should be predefined and may be different for any job. Each operation uses one of the machines to finish one job{u2019}s work for a fixed time interval. Once an operation is preformed by a given machine, it cannot be interrupted before it finishes the operation. Each machine can process only one operation during the time interval. The main purpose of JSSP is commonly used to find the best machine schedule for servicing all jobs. In this dissertation, BA is used to minimize makespan of the JSSP and evaluated its performance besides, comparing the results with Particle Swarm Optimization (PSO) where both BA and PSO are used to minimize makespan for JSSP using some benchmark problems with different size. Finally, the performance of BA is more better than PSO which gives the minimum makespan at the minimum running time. This study shows how the effectiveness and accuracy of the proposed BA in solving JSSP

Issued also as CD