摘要
以企业生产和内部物流为背景,研究生产前半成品运输与无界批处理机生产的协调调度问题.位于存储区的工件由运输机运送到批处理机上进一步加工,批处理机可以同时加工的工件数量不受限制,但是每加工一批工件需要一定的启动费用.目标函数为总完工时间和总启动费用之和的最小化.提出该问题的伪多项式时间算法,进一步给出一般意义NP-难的证明.对于运输时间相等的特殊情况,提出多项式时间的最优算法.
In this paper, a coordinated scheduling problem of transportation of semi-finished jobs and production on a single batching machine is studied. In the transportation part, there are several transporters that transport jobs from a holding area to the single batching machine for further processing. In the production part, the capacity of the batching machine is unbounded. Each batch to be processed on the batching machine incurs a setup cost. The goal is to optimize the sum of the total completion time and total setup cost. For the problem under consideration, a pseudo-polynomial time algorithm is presented. Furthermore, we prove that this problem is NP-hard in the ordinary sense. For the special case with identical transportation times of jobs, an optimal algorithm in polynomial time is given.
出处
《沈阳理工大学学报》
CAS
2009年第2期83-86,共4页
Journal of Shenyang Ligong University
关键词
批处理机
运输
启动费用
NP-难
batching machine
transportation
setup cost
NP-hard
