單機重置問題之完工時間最小化

Abstract

資源重置問題起源於波士頓地區的重建計畫，在重建計畫中的所有大樓都將被改建，居住在其中的居民必須在建築工事開始之前先被安置，波士頓當局必須在有限的安置空間限制下決定大樓的重建順序，讓重建計畫可以早日完工且居民不致於流離失所；在此研究中，所有需改建的大樓被視為工作，而建築工作團隊則視為處理工作的機台，此論文研究最小化單機重置問題的最大完工時間，許多不同的因素被納入考量，被考量的因素包含了工作的釋放時間、學習效應與退化問題、批次機器處理。研究中將會探討問題的複雜度，對一些特殊問題提出最佳解演算法。在討論批次機器時，本研究也將考慮當工作的執行順序都已經給定的情形。

The relocation problem originated from a redevelopment project in the Boston area. In the project, a set of buildings has to be reconstructed. Before a building is demolished, tenants residing in it have to be evacuated and settled at temporary sites. Subject to a limited number of initial housing units, the authority has to determine a processing sequence to successfully redevelop the buildings. This study investigates several variants of the relocation problem in single machine scheduling so as to minimize the makespan. Scheduling with release date constraints and scheduling with time-dependent processing times are studied. The relocation problem on a single batch machine is also addressed. We present problem formulations, give the complexity results, and propose polynomial time algorithms for some special cases.