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 条
  • [31] Multiprocessor task scheduling to minimize the maximum tardiness and the total completion time
    Cai, XQ
    Lee, CY
    Wong, TL
    IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 2000, 16 (06): : 824 - 830
  • [32] Job Scheduling to Minimize Total Completion Time on Multiple Edge Servers
    Fang, Xiaolin
    Cai, Zhipeng
    Tang, Wenyi
    Luo, Guangchun
    Luo, Junzhou
    Bi, Ran
    Gao, Hong
    IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING, 2020, 7 (04): : 2245 - 2255
  • [33] Scheduling a maintenance activity to minimize total weighted completion-time
    Mosheiov, Gur
    Sarig, Assaf
    COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2009, 57 (04) : 619 - 623
  • [34] Scheduling open shops with parallel machines to minimize total completion time
    Naderi, B.
    Ghomi, S. M. T. Fatemi
    Aminnayeri, M.
    Zandieh, M.
    JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2011, 235 (05) : 1275 - 1287
  • [35] Scheduling with non-renewable resources: minimizing the sum of completion times
    Kristóf Bérczi
    Tamás Király
    Simon Omlor
    Journal of Scheduling, 2024, 27 : 151 - 164
  • [36] Scheduling with non-renewable resources: minimizing the sum of completion times
    Berczi, Kristof
    Kiraly, Tamas
    Omlor, Simon
    JOURNAL OF SCHEDULING, 2024, 27 (02) : 151 - 164
  • [37] Uniform parallel machine scheduling with resource consumption constraint
    Yeh, Wei-Chang
    Chuang, Mei-Chi
    Lee, Wen-Chiung
    APPLIED MATHEMATICAL MODELLING, 2015, 39 (08) : 2131 - 2138
  • [38] Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times
    Li Kai & Yang Shanlin School of Management
    Journal of Systems Engineering and Electronics, 2008, (04) : 827 - 834
  • [39] Solving a Malleable Jobs Scheduling Problem to Minimize Total Weighted Completion Times by Mixed Integer Linear Programming Models
    Nhan-Quy Nguyen
    Yalaoui, Farouk
    Amodeo, Lionel
    Chehade, Hicham
    Toggenburger, Pascal
    Intelligent Information and Database Systems, ACIIDS 2016, Pt II, 2016, 9622 : 286 - 295
  • [40] Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times
    Li Kai
    Yang Shanlin
    JOURNAL OF SYSTEMS ENGINEERING AND ELECTRONICS, 2008, 19 (04) : 827 - 834
12345