Heuristic and Exact Algorithms for the Two-Machine Just in Time Job Shop Scheduling Problem

Abstract EN

The problem addressed in this paper is the two-machine job shop scheduling problem when the objective is to minimize the total earliness and tardiness from a common due date (CDD) for a set of jobs when their weights equal 1 (unweighted problem).

This objective became very significant after the introduction of the Just in Time manufacturing approach.

A procedure to determine whether the CDD is restricted or unrestricted is developed and a semirestricted CDD is defined.

Algorithms are introduced to find the optimal solution when the CDD is unrestricted and semirestricted.

When the CDD is restricted, which is a much harder problem, a heuristic algorithm is proposed to find approximate solutions.

Through computational experiments, the heuristic algorithms’ performance is evaluated with problems up to 500 jobs.