CAJ | 학술논문

研究工件带有到达时间且机器带有可用性限制(禁用区间)的单机平行批排序问题.假设机器在一些不交的时间区间上不可用.工件以平行批的形式在机器可用的时间区间上加工,并且不可中断.一个批的加工时间是这一批中加工时间最长的工件的加工时间.对任意的正则目标函数,当工件带有到达时间且机器带有可用性限制时,给出了单机平行批排序问题的一个拟多项式时间算法.
연구공건대유도체시간차궤기대유가용성한제(금용구간)적단궤평행비배서문제.가설궤기재일사불교적시간구간상불가용.공건이평행비적형식재궤기가용적시간구간상가공,병차불가중단.일개비적가공시간시저일비중가공시간최장적공건적가공시간.대임의적정칙목표함수,당공건대유도체시간차궤기대유가용성한제시,급출료단궤평행비배서문제적일개의다항식시간산법.
The single machine parallel-batch scheduling with release dates and machine availability constraints is con-sidered. There are some disjoint intervals in which the machine cannot be available. The jobs are processed in batches form in the remaining free time-slots without preemption, where the processing time of batch is defined to be the maximum processing time of the jobs in this batch. The pseudopolynomial solvability of the unbounded batch machine scheduling problem with job release dates and machine availability constraints is established for every regular objective.