RESOURCE LOADING:APPLICATIONS AND COMPLEXITY ANALYSIS

摘要：

　　This paper studies the resource loading problem,which consists of a set of jobs that must be scheduled within a given time horizon that is organized into consecutive time periods,where each period is associated with a fixed number of available workers.The objective is to find a feasible schedule that minimizes the number of additional workers needed to execute all the jobs.We describe how this problem arises in industry,and we study six special cases.We present polynomial algorithms for the easy cases and pseudo-polynomial algorithms for weakly NP-hard cases,and we study the approximation of the strongly NP-hard subproblems.

关键词： resource loading dynamic programming approximation algorithms NP-hard

作者: Fabrice Talla Nobibon Roel Leus Kameng Nip Zhenbo Wang

作者单位: ORSTAT, Faculty of Economics and Business, KU Leuven, 3000 Leuven, Belgium Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China

会议类型: 国际会议

会议名称: 11th International Symposium on Operations Research and its Applications(第11届运筹学及其应用国际研讨会)

会议地点: 安徽黄山

会议语种:英文

页码: 14-18

在线出版日期: 2013-08-23（万方平台首次上网日期，不代表论文的发表时间）