A combination of evolutionary algorithm, mathematical programming, and a new local search procedure for the just-in-time job-shop scheduling problem

This paper presents a combination of evolutionary algorithm and mathematical programming with an efficient local search procedure for a just-in-time job-shop scheduling problem (JITJSSP). Each job on the JITTSSP is composed by a sequence of operations, each operation having a specific machine where it must be scheduled and a due date when it should be completed. There is a tardiness cost if an operation is finished later than its due date and also an earliness cost if finished before. The objective is to find a feasible scheduling obeying precedence and machine constraints, minimizing the total earliness and tardiness costs. The experimental results with instances from the literature show the efficiency of the proposed hybrid method: it was able to improve the known upper bound for most of the instances tested, in very little computational time.