CAJ | 학술논문

工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.本文讨论了在单机上,加工带准备时间与强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过奇偶划分问题归约,证明了其是NP-complete的.而后,讨论了加工时间相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序,因此提出了一个多项式时间算法,既能判定可行性,又能针对可行问题获得最优排序.
공건대강제공기,지공건필수재이급정적공기내완공,불득연지.저충배경재실제응용중수처가견.여과공건과조제전완공,의미착공건환수요보관,장회산생액외비용.본문토론료재단궤상,가공대준비시간여강제공기적n개가중단공건,재궤기가공한조건하,학정일개공건배서,사득제전완공시간화최소.선고필료문제적복잡성,통과기우화분문제귀약,증명료기시NP-complete적.이후,토론료가공시간상등적특수정형,유우공건불윤허연지,문제가능회무가행배서,인차제출료일개다항식시간산법,기능판정가행성,우능침대가행문제획득최우배서.