Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/43312
Title: Triangle structure diagrams for a single machine batching problem with identical jobs
Authors: Li, S
Li, M
Yan, H 
Keywords: Batching
Scheduling
Single machine
Triangle structure
Issue Date: 2014
Publisher: Springer
Source: Advances in difference equations, 2014, v. 2014, no. 1, 71 How to cite?
Journal: Advances in difference equations 
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.
URI: http://hdl.handle.net/10397/43312
ISSN: 1687-1839 (print)
1687-1847 (online)
DOI: 10.1186/1687-1847-2014-71
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

30
Last Week
6
Last month
Checked on Sep 25, 2017

Google ScholarTM

Check

Altmetric



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