CAJ | 학술논문

本文考虑货物装卸管理中船主和港口之间的下述相互制约关系:有n条船在同一时刻到达同一港口,因而也希望在同一时刻完成装卸货物.如某船的货物不能如期装卸完,船主会向港方索取赔偿,反之,如货物提前装卸完,则船主会向港方付取奖金.因此从港方来说要适当考虑n条船的一个装卸程序以使总费用最少.对这样一个NP-困难的排序问题,本文给出了一个动态规划解法,且在逆一致性条件下给出了一伪多项式时间的动态规划解法.
본문고필화물장사관리중선주화항구지간적하술상호제약관계:유n조선재동일시각도체동일항구,인이야희망재동일시각완성장사화물.여모선적화물불능여기장사완,선주회향항방색취배상,반지,여화물제전장사완,칙선주회향항방부취장금.인차종항방래설요괄당고필n조선적일개장사정서이사총비용최소.대저양일개NP-곤난적배서문제,본문급출료일개동태규화해법,차재역일치성조건하급출료일위다항식시간적동태규화해법.
This paper considers such a sequencing problem which comes from the relationshipbetween captain and harbor in loading and unloading goods: n ships arrive at the oneharbor at the same time, and also hope to finish their loading and unloading goods at thesame time. For a given ship, if the harbor couldn't finish its loading and unloading goodsbefore or at its due date, the harbor will be fined by the captain; otherwise the captain willreward the harbor. Thus the harbor needs to arrange the loading and unloading sequenceoptimally for these ships such that the total cost is minimized. Corresponding to sucha NP-hard problem, this paper gives a dynamic programming and developes a pseudo-polynomial dynamic programming algorithm under inverse agreeable ratio condition.