在制造系统和半导体流水线上经常需要考虑的是在线继列分批问题。本文所考虑的问题中，每个工件具有各自的安装时间和加工时间(s, p)，属于同一组的工件才能在同一批中加工，每一批最多可以加工b个工件，批的安装时间和加工时间分别为这一批中工件的最大安装时间和加工时间之和，目标函数是最小化工件的最大完工时间。利用对手法证明了任何一个在线算法的竞争比都不小于max{b2b+1,1+α}，且给出了一个渐近意义下最好的竞争比是2的在线算法。%There are many on-line serial-batching problems in cellular manufacturing system and semiconductor production lines system. In this paper, each job has its process-ing time and setup time (s, p), the jobs belonged to the same family are processed in the same batch, the number of jobs processed in the same batch is at most b, the setup time and the processing time of the batch is respectively the maximum setup time and the total processing times of all jobs in this batch. The objective is to minimize the maximum completion time of the jobs (makespan). By the adver-sary method, there exists no on-line algorithm with a competitive ratio less than max{b2b+1 , 1+α}, and asymptotically a best on-line algorithm with a competitive ratio of 2 is presented.
展开▼
