@inproceedings{b6e1829d1e73449bbdf818a166325272,
title = "Heuristics for parallel machine scheduling with deterioration effect",
abstract = "This paper considers one parallel machine scheduling problem in which the processing time of a job is a simple linear increasing function of its starting time. The objective is to minimize the makespan, and our focus is on the case with an arbitrary number of parallel machines. We prove that LIST rule is (1 + bmax)m-1/m -approximation where m is the number of machines and bmax is the maximum deteriorating rate of job. We then propose one heuristic LDR (Largest deteriorating Rate first). The heuristic is proved (1 + bmin)m-1/m -approximation where b min is the minimum deteriorating rate. We further show that this ratio is tight when m = 2,3 and 4.",
keywords = "Approximation, Makespan, Parallel machine, Scheduling, Simple linear deterioration",
author = "Ming Liu and Feifeng Zheng and Yinfeng Xu and Lu Wang",
year = "2011",
doi = "10.1007/978-3-642-22616-8\_4",
language = "英语",
isbn = "9783642226151",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "46--51",
booktitle = "Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings",
note = "5th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2011 ; Conference date: 04-08-2011 Through 06-08-2011",
}