Title :
Dynamic programming for single batching machine with total weighted completion time
Author :
Feng, Daguang ; Liu, Peng ; Wu, Suwen ; Liu, Bo
Author_Institution :
Sci. of Inst., Shenyang Agric. Univ., Shenyang, China
Abstract :
The problem of total weighted completion time for single batching machine is an open problem until now. Accordingly, heuristics is very useful to the problem. We construct a nonlinear mathematical model for the problem with unbounded batching machine. A dynamic programming is also carried for the problem, which is proved to be at most 2 times of the optimal solution later. With an example, we show that the bound is tight.
Keywords :
dynamic programming; single machine scheduling; dynamic programming; nonlinear mathematical model; single batching machine; total weighted completion time; unbounded batching machine; Annealing; Coils; Dynamic programming; Furnaces; Integrated circuit manufacture; Manufacturing industries; Mathematical model; Metals industry; Steel; Technology management; batching machine; dynamic programming; worst case;
Conference_Titel :
Control and Decision Conference (CCDC), 2010 Chinese
Conference_Location :
Xuzhou
Print_ISBN :
978-1-4244-5181-4
Electronic_ISBN :
978-1-4244-5182-1
DOI :
10.1109/CCDC.2010.5498479
