CAJ | 학술논문

研究关于有固定工件序约束的单机最小化最大流程排序问题模型.在该模型中,有些固定工件已事先安排好,其余的自由工件之间的加工顺序满足给定的序约束.工件之间不允许抢先中断,在同一时间,机器最多只能加工一个工件.其目标是使得最大流程达到最小.该问题即使是对没有序约束的特殊情形也已被证明是NP-困难的.给出了该问题的一个线性时间的2-近似算法,并且证明了除非P=NP,对任意的δ>0,该问题甚至没有拟多项式时间的(2-δ)-近似算法.
연구관우유고정공건서약속적단궤최소화최대류정배서문제모형.재해모형중,유사고정공건이사선안배호,기여적자유공건지간적가공순서만족급정적서약속.공건지간불윤허창선중단,재동일시간,궤기최다지능가공일개공건.기목표시사득최대류정체도최소.해문제즉사시대몰유서약속적특수정형야이피증명시NP-곤난적.급출료해문제적일개선성시간적2-근사산법,병차증명료제비P=NP,대임의적δ>0,해문제심지몰유의다항식시간적(2-δ)-근사산법.
The single machine scheduling problem to minimize makespan with fixed jobs and precedence constraints is considered. There are some fixed jobs which are already fixed in the schedule. The remaining free jobs are to be assigned to the machines in such a way that they do not overlap with the fixed jobs. The order of job processing between the free jobs is restricted by given precedence constraints , and the jobs are processed without preemption. The objective is to minimize the makespan. In the literature this problem has been proved to be strongly NP-hard even without precedence constraints. It is shown that this problem has a linear-time 2-approximation algorithm, but has no pseudopolynomial-time (2-δ)-approximation algorithm, for every δ>0, if P≠NP.