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.
Original language | English |
---|---|
Article number | 71 |
Journal | Advances in Difference Equations |
Volume | 2014 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Jan 2014 |
Keywords
- Batching
- Scheduling
- Single machine
- Triangle structure
ASJC Scopus subject areas
- Applied Mathematics
- Algebra and Number Theory
- Analysis