Adaptation ofDiscrepancy-based Methods forSolving HybridFlowShopProblems

This paper investigates howtoadapt some discrepancy-based search methods tosolve Hybrid FlowShop(HFS) problems inwhicheachstageconsists ofseveral identical machines operating inparallel. Theobjective istodetermine a schedule that minimizes themakespan. We present here an adaptation oftheDepth-bounded Discrepancy Search (DDS)method toobtain solutions withmakespan ofhighquality. Thisadaptation fortheHFScontains no redundancy forthesearch treeexpansion. Toimprove thesolutions ofourHFSproblem, we proposealocal search method, called CDDS,whichisahybridization oftwoexisting discrepancy-based methods (DDSandClimbing Discrepancy Search). CDDS introduces an intensification processaround promising solutions. Thesemethods aretested on benchmark problems. Results showthat discrepancy methods give promising results.