Title: Efficient local search algorithms for job-shop scheduling problems

Authors: Pisut Pongchairerks

Addresses: Faculty of Engineering, Industrial Engineering Programme, Thai-Nichi Institute of Technology, 1771/1 Pattanakarn Rd., Suanluang, Bangkok, 10250, Thailand

Abstract: To solve job-shop scheduling problems, this paper develops four local search algorithms based on an input parameter of controlling the maximum allowable delay times of all machines. The use of this parameter in different values can change the size in numbers of the algorithm's solution space. The first proposed algorithm fixes the mentioned parameter's value and generates only forward schedules. The second algorithm reduces the parameter value iteratively and generates only forward schedules. The third algorithm reduces the parameter value iteratively; in addition, each operation-based permutation generated by this algorithm is transformed into both forward and backward schedules simultaneously. The fourth algorithm in the first-half iterations reduces the parameter value iteratively as well as generating only forward schedules; after that, this algorithm in the second-half iterations increases the parameter value iteratively as well as generating only backward schedules.

Keywords: local search; job shop scheduling problem; JSP; parameterised active schedules; forward schedules; backward schedules; makespan; active schedules.

DOI: 10.1504/IJMOR.2016.077995

International Journal of Mathematics in Operational Research, 2016 Vol.9 No.2, pp.258 - 277

Received: 16 Sep 2014
Accepted: 11 Oct 2014
Published online: 31 Jul 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article