Fabrication scheduling on a single machine with due date constraints

Bertrand M.T. Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


There is a fabrication machine available for processing a set of jobs. Each job is associated with a due date and consists of two parts, one is common among all products and the other is unique to itself. The unique components are processed individually and the common parts are grouped into batches for processing. A constant setup time is incurred when each batch is formed. The completion time of a job is defined as the time when both of its unique and common components are completed. In this paper, we consider two different objectives. The first problem seeks to minimize the maximum tardiness, and the second problem is to minimize the number of tardy jobs. To minimize the maximum tardiness, we propose a dynamic programming algorithm that optimally solves the problem in polynomial time. Next, we show NP-hardness proof and design a pseudo-polynomial time dynamic programming algorithm for the problem of minimizing the number of tardy jobs.

Original languageEnglish
Pages (from-to)95-105
Number of pages11
JournalEuropean Journal of Operational Research
Issue number1
StatePublished - 1 Jan 2002


  • Batch processing
  • Dynamic programming
  • Maximum tardiness
  • NP-hardness
  • Number of tardy jobs
  • Scheduling

Fingerprint Dive into the research topics of 'Fabrication scheduling on a single machine with due date constraints'. Together they form a unique fingerprint.

Cite this