Scheduling jobs on a single machine with inventory operations
In the classical scheduling problems, it is always assumed that jobs would be delivery immediately when they are completed. However, in many production-distribution systems, the jobs are required to be delivered by their due date but completed times. Then those jobs completed ahead of their due dates must be stored. In this paper, we consider the single machine scheduling problem with inventory operations. The objective is to minimize makespan subject to minimize ΣUj. We show the problem is strongly NP-hard. A polynomial 2-approximation scheme for the problem is presented and a special case of the problem, in which each job is one unit in size, is provided an optimal algorithm.
scheduling strongly NP-hard approximation algorithm performance ratio makespan
Bao-Qiang Fan Guo-Chun Tang Shu-Xia Zhang
Department of Mathematics, Ludong University, Yantai, Shandong 264025, China Institute of Management Engineering, Shanghai Second Polytechnic University, Shanghai 201209, China Department of Watercraft Command(c)(n)Zhenjiang Watercraft College, Zhenjiang, Jiangsu 212003, China
国际会议
The Seventh International Symposium(ISORA08)(第七届国际效力研究及其应用学术会议)
云南丽江
英文
344-350
2008-10-31（万方平台首次上网日期，不代表论文的发表时间）