SCHEDULING TO MINIMIZE THE TOTAL RESOURCE CONSUMPTION WITH A CONSTRAINT ON THE SUM OF COMPLETION TIMES

被引：19
|
作者：
LI, CL
机构：
[1] John M. Olin School of Business, Washington University, St. Louis
来源：
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1995年 / 80卷 / 02期
关键词：
SCHEDULING; SEQUENCING; RELEASE DATES; RESOURCE ALLOCATION;
D O I：
10.1016/0377-2217(93)E0255-V
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
We consider the problem of scheduling a set of jobs on a single machine where the release time of a job is related to the amount of resource consumed. The objective is to minimize the total amount of resource consumed subject to a constraint on the sum of completion times of the jobs. We show that the problem is NP-hard in general and can be solved efficiently when the resource consumption function is linear. The parallel machine case is also discussed.
引用
收藏
页码：381 / 388
页数：8
相关论文
共 50 条
  • [21] Online scheduling with linear deteriorating jobs to minimize the total weighted completion time
    Ma, Ran
    Tao, Jiping
    Yuan, Jinjiang
    APPLIED MATHEMATICS AND COMPUTATION, 2016, 273 : 570 - 583
  • [22] Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times
    Yokoyama, M
    Santos, DL
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2005, 161 (03) : 754 - 770
  • [23] A flowshop scheduling algorithm to minimize total weighted completion time
    Zhao, CL
    Zhang, QL
    Tang, HY
    PROCEEDINGS OF THE 4TH WORLD CONGRESS ON INTELLIGENT CONTROL AND AUTOMATION, VOLS 1-4, 2002, : 1485 - 1488
  • [24] Scheduling to minimize the maximum total completion time per machine
    Wan, Long
    Ding, Zhihao
    Li, Yunpeng
    Chen, Qianqian
    Tan, Zhiyi
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 242 (01) : 45 - 50
  • [25] Two-agent singe-machine scheduling with release times to minimize the total weighted completion time
    Cheng, T. C. E.
    Chung, Yu-Hsiang
    Liao, Shan-Ci
    Lee, Wen-Chiung
    COMPUTERS & OPERATIONS RESEARCH, 2013, 40 (01) : 353 - 361
  • [26] Two-machine flowshop scheduling problem to minimize total completion time with bounded setup and processing times
    Allahverdi, A
    INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2006, 103 (01) : 386 - 400
  • [27] The benefit of preemption for single machine scheduling so as to minimize total weighted completion time
    Epstein, Leah
    Levin, Asaf
    OPERATIONS RESEARCH LETTERS, 2016, 44 (06) : 772 - 774
  • [28] NP-hardness of the single-variable-resource scheduling problem to minimize the total weighted completion time
    Yuan, J. J.
    Cheng, T. C. E.
    Ng, C. T.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 178 (02) : 631 - 633
  • [29] Open shop scheduling problem to minimize total weighted completion time
    Bai, Danyu
    Zhang, Zhihai
    Zhang, Qiang
    Tang, Mengqian
    ENGINEERING OPTIMIZATION, 2017, 49 (01) : 98 - 112
  • [30] Online scheduling of a single machine to minimize total weighted completion time
    Anderson, EJ
    Potts, CN
    MATHEMATICS OF OPERATIONS RESEARCH, 2004, 29 (03) : 686 - 697
12345