Multiple machine JIT scheduling: A tabu search approach

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)4899-4915
Number of pages17
JournalInternational Journal of Production Research
Issue number21
StatePublished - Nov 2007

All Science Journal Classification (ASJC) codes

  • Strategy and Management
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Multiple machine JIT scheduling: A tabu search approach'. Together they form a unique fingerprint.

Cite this