期刊
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
卷 60, 期 10, 页码 3170-3181出版社
TAYLOR & FRANCIS LTD
DOI: 10.1080/00207543.2021.1912430
关键词
Scheduling; single machine; total earliness and tardiness; non-renewable resource
This study addresses a class of resource-constrained scheduling problems with non-renewable resources supplied in different periods, aiming to minimize total tardiness and total earliness. The optimal schedules are discussed and a tractable algorithm is developed, showing promising performance guarantee in scalability tests.
We consider a special class of resource-constrained single machine scheduling problems. In the classical scheduling context, resource types are classified into renewable and non-renewable; however, a large variety of real-world problems may not fit into one of these classes, e.g. labour regulations in project scheduling, budget allocation to different phases of a construction project, and dose management in a medical imaging centre. In this study, we address a class of non-renewable resources supplied, not necessarily immediately, in different periods of the planning horizon. The objective is to assign the jobs to the supply periods and schedule them such that the sum of total tardiness and total earliness is minimised. Several properties and complexity results of the optimal schedules are discussed, then they are used to develop a tractable algorithm. First, we decompose the problem into several single supply problems and then decide the optimal schedule through a polynomial-time optimal algorithm for each single supply problem. The scalability tests indicate the promising performance guarantee of the algorithm compared to provably optimal schedules in the integrated framework.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据