计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2013年
9期
1880-1888
,共9页
可计算性%装箱%调度%优化%NP难度
可計算性%裝箱%調度%優化%NP難度
가계산성%장상%조도%우화%NP난도
computability%packing%scheduling%optimization%NP hard
提出了四维时空中考虑时间因素的一个长方体装箱工作的优化调度问题.已知一个形状大小任意给定的长方体形的箱子和有限个形状大小分别任意给定的长方体形的刚性物体,又知每个物体须在箱中连续烘烤的时间长度,问应如何安排每个物体的入箱时刻,以及至出箱前这段时间内它在每个时刻上的位置和方向,才能使整个箱子的被使用时间最少.问题中涉及的箱子及诸长方形刚体的长、宽、高以及各刚体须连续烘烤的时间长度均为分别任意给定的正实数.与经典装箱问题的不同之处在于,各物体在箱子内可以随时间而改变其位置和方向,从而使四维时空得到更真实、更充分的利用.进一步地,通过枚举长方体的各种排列,并证明对每一种排列,按照某种贪心策略可得到该排列下问题的最优解,从而给出了原问题具有可计算性的严格证明.在此基础上,今后有望对此问题发展出各种有效的实用求解算法.
提齣瞭四維時空中攷慮時間因素的一箇長方體裝箱工作的優化調度問題.已知一箇形狀大小任意給定的長方體形的箱子和有限箇形狀大小分彆任意給定的長方體形的剛性物體,又知每箇物體鬚在箱中連續烘烤的時間長度,問應如何安排每箇物體的入箱時刻,以及至齣箱前這段時間內它在每箇時刻上的位置和方嚮,纔能使整箇箱子的被使用時間最少.問題中涉及的箱子及諸長方形剛體的長、寬、高以及各剛體鬚連續烘烤的時間長度均為分彆任意給定的正實數.與經典裝箱問題的不同之處在于,各物體在箱子內可以隨時間而改變其位置和方嚮,從而使四維時空得到更真實、更充分的利用.進一步地,通過枚舉長方體的各種排列,併證明對每一種排列,按照某種貪心策略可得到該排列下問題的最優解,從而給齣瞭原問題具有可計算性的嚴格證明.在此基礎上,今後有望對此問題髮展齣各種有效的實用求解算法.
제출료사유시공중고필시간인소적일개장방체장상공작적우화조도문제.이지일개형상대소임의급정적장방체형적상자화유한개형상대소분별임의급정적장방체형적강성물체,우지매개물체수재상중련속홍고적시간장도,문응여하안배매개물체적입상시각,이급지출상전저단시간내타재매개시각상적위치화방향,재능사정개상자적피사용시간최소.문제중섭급적상자급제장방형강체적장、관、고이급각강체수련속홍고적시간장도균위분별임의급정적정실수.여경전장상문제적불동지처재우,각물체재상자내가이수시간이개변기위치화방향,종이사사유시공득도경진실、경충분적이용.진일보지,통과매거장방체적각충배렬,병증명대매일충배렬,안조모충탐심책략가득도해배렬하문제적최우해,종이급출료원문제구유가계산성적엄격증명.재차기출상,금후유망대차문제발전출각충유효적실용구해산법.
