Triangle structure diagrams for a single machine batching problem with identical jobs

Shanlin Li, Maoqin Li, Hong Yan

Research output: Journal article publicationJournal articleAcademic researchpeer-review


The problem of batching identical jobs on a single machine to minimize the completion time is studied by employing the difference analysis technique. Constant processing times and batch setup times are assumed. We first establish the relation between the optimal solution and the first-order difference of the optimal objective function in terms of the number of jobs and investigate the properties of the first-order difference. Then we obtain the triangle structure diagram of the batching problem in O( √ n) time at most by using the permutation of some numbers which describe the character of the first-order difference. The diagrams enable us to see clearly the specific expressions of optimal solutions for the n-jobs batching problem and any m-jobs batching problem simultaneously, where m ≤ n. Also,we showthat the result proposed by Santos (MSc thesis, 1984) and Santos and Magazine (Oper. Res. Lett. 4:99-103, 1985) is a special case of our result.
Original languageEnglish
Article number71
JournalAdvances in Difference Equations
Issue number1
Publication statusPublished - 1 Jan 2014


  • Batching
  • Scheduling
  • Single machine
  • Triangle structure

ASJC Scopus subject areas

  • Applied Mathematics
  • Algebra and Number Theory
  • Analysis


Dive into the research topics of 'Triangle structure diagrams for a single machine batching problem with identical jobs'. Together they form a unique fingerprint.

Cite this