AN APPLICATION OF THE BIN-PACKING TECHNIQUE TO JOB SCHEDULING ON UNIFORM PROCESSORS

被引：5
|
作者：
VANDEVEL, H
SHIJIE, S
机构：
来源：
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY | 1991年 / 42卷 / 02期
关键词：
BIN PACKING; MINIMUM MAKESPAN; SCHEDULING; UNIFORM PROCESSOR;
D O I：
10.1038/sj/jors/0420210
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
A non-polynomial algorithm is presented for solving the minimum makespan problem on a set of uniform machines. This algorithm uses the bin-packing technique and provides an approximate solution which turns into an optimal one when the relative error is chosen small enough.
引用
收藏
页码：169 / 172
页数：4
相关论文
共 50 条
  • [1] APPLICATION OF BIN-PACKING TO MULTIPROCESSOR SCHEDULING
    COFFMAN, EG
    GAREY, MR
    JOHNSON, DS
    SIAM JOURNAL ON COMPUTING, 1978, 7 (01) : 1 - 17
  • [2] A hybrid bin-packing heuristic to multiprocessor scheduling
    Alvim, ACF
    Ribeiro, CC
    EXPERIMENTAL AND EFFICIENT ALGORITHMS, 2004, 3059 : 1 - 13
  • [3] BIN-PACKING ALGORITHMS FOR PERIODIC TASK SCHEDULING
    Zhu, Zhilin
    Sui, Jinxue
    Yang, Li
    INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, 2011, 25 (07) : 1147 - 1160
  • [4] BIN-PACKING
    WAGON, S
    MATHEMATICAL INTELLIGENCER, 1985, 7 (04): : 65 - 68
  • [5] The Price of Clustering in Bin-Packing with Applications to Bin-Packing with Delays
    Azar, Yossi
    Emek, Yuval
    van Stee, Rob
    Vainstein, Danny
    SPAA'19: PROCEEDINGS OF THE 31ST ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURESS, 2019, 2019, : 1 - 10
  • [6] Algorithm for Crew-Scheduling Problem with Bin-Packing Features
    Qiao, Wenxin
    Hamedi, Masoud
    Haghani, Ali
    TRANSPORTATION RESEARCH RECORD, 2010, (2197) : 80 - 88
  • [7] A typical problem of bin-packing
    Figueroa Mata, Geovanni
    Carrera Retana, Ernesto
    TECNOLOGIA EN MARCHA, 2011, 24 (02): : 34 - 43
  • [8] ON A GENERALIZED BIN-PACKING PROBLEM
    LEWIS, RT
    PARKER, RG
    NAVAL RESEARCH LOGISTICS, 1982, 29 (01) : 119 - 145
  • [9] BIN-PACKING IN 1.5 DIMENSION
    HOYLAND, SO
    LECTURE NOTES IN COMPUTER SCIENCE, 1988, 318 : 129 - 137
  • [10] BIN-PACKING BY SIMULATED ANNEALING
    RAO, RL
    IYENGAR, SS
    COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1994, 27 (05) : 71 - 82
12345