《2016 A Simple Optimised Search Heuristic for the Job Shop Scheduling Problem》.pdf

13 A Simple Optimised Search Heuristic for the Job Shop Scheduling Problem Susana Fernandes1 and Helena R. Louren¸co2 1 Universidade do Algarve, Faro, Portugal sfer@ualg.pt 2 Univertitat Pompeu Fabra, Barcelona, Spain helena.ramalhinho@ Summary. This paper presents a simple Optimised Search Heuristic for the Job Shop Scheduling problem that combines a GRASP heuristic with a branch-and-bound algo- rithm. The proposed method is compared with similar approaches and leads to better results in terms of solution quality and computing times. Keywords: Job-Shop Scheduling, Hybrid Metaheuristic, Optimised Search Heuristics, GRASP, Exact Methods. 13.1 Introduction The job shop scheduling problem has been known to the operations research community since the early 50’s [392]. It is considered a particularly hard com- binatorial optimisation problem of the NP-hard class [391] and it has numerous practical applications; which makes it an excellent test problem for the quality of new scheduling algorithms. These are main reasons for the vast bibliography on both exact and heuristic methods applied to this particular scheduling problem. The paper of Jain and Meeran, [392], includes an exhaustive survey not only of the evolution of the definition of the problem, but also of all the techniques applied to it. Recently a new class of procedures that combine local search based (meta) heuristics and exact algorithms have been developed, we denominate them Op- timised Search Heuristics (OSH) [389]. This paper presents a simple OSH procedure for the job shop scheduling prob- lem that combines a GRASP heuristic with a branch-and-bound algorithm. In the next section, we introduce the job shop scheduling problem. In section 13.3, we present a short review of existent OSH methods applied to this problem and in section 13.4 we describe in detail the OSH method developed. In section