A Hybrid Bubble Sorting Simulated Annealing Algorithm for Job Shop Scheduling

Scheduling can be defined as a problem of finding an optimal sequence to execute a finite set of operations satisfying most of the constraints. So they are generally treated as NP - complete combinatorial optimization problems. Exact methods such as the branch and bound method and dynamic programming take considerable computing time if an optimum solution exists. Stochastic search techniques can be used to find nearby optimal solution. This paper presents one such technique such as Hybrid Bubble Sorting Simulated Annealing Technique (HBSSAT), a Meta - heuristic to solve the job-shop scheduling which presents two difficulties: the first is the assignment of each operation to a machine, and the other is the scheduling of set of operations in order to minimize the criterion ( e. g. the make span). Sorting is done first before generation of initial solution which further gives the multiple optimal solutions with minimum computational time.