期刊
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE
卷 65, 期 -, 页码 41-54出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.omega.2015.12.006
关键词
Approximation algorithm; FPTAS; Bicriteria scheduling
资金
- Natural Sciences and Engineering Research Council of Canada [1798-2008]
We study a single-machine scheduling problem in a flexible framework, where both job processing times and due dates are decision variables controllable by the scheduler. Our objective is to provide a practical tool for managers to optimally (or approximately) coordinate higher level decisions (such as delivery date quotation) with lower level (operational) decisions (such as scheduling and resource allocation). We analyze the problem for two due date assignment methods and a convex resource consumption function. For each due date assignment method, we provide a bicriteria analysis where the first criterion is to minimize the total weighted number of tardy jobs plus due date assignment cost, and the second criterion is to minimize total weighted resource consumption. These bicriteria problems are known to be NP-hard. In this paper, for each due date assignment method, we develop pseudo-polynomial algorithm and fully polynomial time approximation scheme (FPTAS) to minimize the total weighted number of tardy jobs plus due date assignment costs subject to an upper bound on the total weighted resource consumption. (C) 2015 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据