Parallel-machine batch scheduling to minimize the maximum lateness and the number of tardy jobs

Bertrand M.T. Lin*, A. A.K. Jeng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

37 Scopus citations


There is a set of jobs available to process in batches on a set of identical parallel machines. A sequence-independent setup time is incurred whenever a batch is formed on any machine. The jobs in the same batch are continuously processed after the setup. The processing length of a batch is the sum of the setup time and the processing times of the jobs it contains. Under the batch availability constraint, the completion time of a job is defined as the time when the batch it belongs to is totally completed. With each job, a due date is specified for its completion. In this paper, we first consider the problem to schedule as well as group the jobs so that the maximum lateness is minimized. The second problem is to minimize the number of tardy jobs. We first design dynamic programming algorithms for finding optimal solutions to the two problems. Then, we design several heuristics and conduct computational experiments to study their relative performance.

Original languageEnglish
Pages (from-to)121-134
Number of pages14
JournalInternational Journal of Production Economics
Issue number2
StatePublished - 28 Sep 2004


  • Batch scheduling
  • Due date
  • Dynamic program
  • Heuristics
  • Maximum lateness
  • Number of tardy jobs
  • Parallel-machine

Fingerprint Dive into the research topics of 'Parallel-machine batch scheduling to minimize the maximum lateness and the number of tardy jobs'. Together they form a unique fingerprint.

Cite this