Please use this identifier to cite or link to this item:
Title: Triangle structure diagrams for a single machine batching problem with identical jobs
Authors: Li, S
Li, M
Yan, H 
Issue Date: 2014
Source: Advances in difference equations, 2014, v. 2014, 71, p. 1-20
Abstract: 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.
Keywords: Batching
Single machine
Triangle structure
Publisher: Springer
Journal: Advances in difference equations 
ISSN: 1687-1839 (print)
1687-1847 (online)
DOI: 10.1186/1687-1847-2014-71
Rights: ©2014 Li et al.; licensee Springer. This is an Open Access article distributed under the terms of the Creative Commons Attribu-tion License (, which permits unrestricted use, distribution, and reproduction in anymedium, provided the original work is properly cited.
The following publication Li, S., Li, M., & Yan, H. (2014). Triangle structure diagrams for a single machine batching problem with identical jobs. Advances in Difference Equations, 2014, 71, 1-20 is available at
Appears in Collections:Journal/Magazine Article

Files in This Item:
File Description SizeFormat 
Li_Triangle_Single_Machine.pdf411.58 kBAdobe PDFView/Open
View full-text via PolyU eLinks SFX Query
Show full item record
PIRA download icon_1.1View/Download Full Text

Page view(s)

Last Week
Last month
Citations as of Sep 23, 2020


Citations as of Sep 23, 2020

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.