Multiple machine JIT scheduling: a tabu search approach

Abstract

This paper presents an approach to solving the multiple machine, non-preemptive, earliness-tardiness scheduling problem with unequal due dates in a flow shop with machine tiers (FMT). In this variant of the flow shop problem, machines are arranged in tiers or groups, and the jobs must visit one machine in each tier. The processing times, machine assignments, and due dates are deterministic and known in advance. The objective is to find a permutation schedule that minimizes the total deviation of each job from its due date. A tabu search (TS) meta-heuristic combined with an LP evaluation function is applied to solve this problem and results are compared to optimal permutation solutions for small problems and the earliest due date schedule for large problems. Several neighborhood generation methods and two diversification strategies are examined to determine their effect on solution quality. Results show that the TS method works well for this problem. TS found the optimal solution in all but one of the small problem instances and improved the earliest due date solutions for larger instances where no optimal solutions could be found.