Lower Bounds for Scheduling on Identical Parallel Machines with Heads and Tails

被引：2
|
作者：
Mohamed Haouari
Anis Gharbi
机构：
[1] Ecole Polytechnique de Tunisie,Laboratory of Mathematical Engineering
来源：
Annals of Operations Research | 2004年 / 129卷
关键词：
scheduling; identical parallel machines; release dates; delivery times; makespan; lower bound;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In this paper, we investigate new lower bounds for the P|rj,qj|Cmax scheduling problem. A new bin packing based lower bound, as well as several new lifting procedures are derived for this strongly NP -hard problem. Extensive numerical experiments show that the proposed lower bounds consistently outperform the best existing ones.
引用
收藏
页码：187 / 204
页数：17
相关论文
共 50 条
  • [41] Optimal preemptive scheduling on a fixed number of identical parallel machines
    Moukrim, A
    Quilliot, A
    OPERATIONS RESEARCH LETTERS, 2005, 33 (02) : 143 - 150
  • [42] On discrete lot-sizing and scheduling on identical parallel machines
    C. Gicquel
    L. A. Wolsey
    M. Minoux
    Optimization Letters, 2012, 6 : 545 - 557
  • [43] Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines
    Leah Epstein\thanks{School of Computer Science, The Interdisciplinary Center, Herzliya, Israel. lea@idc.ac.il.
    Jiri Sgall
    Algorithmica , 2004, 39 : 43 - 57
  • [44] Approximation schemes for scheduling on uniformly related and identical parallel machines
    Epstein, L
    Sgall, J
    ALGORITHMICA, 2004, 39 (01) : 43 - 57
  • [45] On discrete lot-sizing and scheduling on identical parallel machines
    Gicquel, C.
    Wolsey, L. A.
    Minoux, M.
    OPTIMIZATION LETTERS, 2012, 6 (03) : 545 - 557
  • [46] Preemptive scheduling on two identical parallel machines with a single transporter
    Kellerer, Hans
    Soper, Alan J.
    Strusevich, Vitaly A.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2013, 25 (02) : 279 - 307
  • [47] Scheduling equal-length jobs on identical parallel machines
    Baptiste, P
    DISCRETE APPLIED MATHEMATICS, 2000, 103 (1-3) : 21 - 32
  • [48] Scheduling jobs with shared additional operations on parallel identical machines
    Zinder, Yakov
    Berlinska, Joanna
    Lin, Bertrand M. T.
    COMPUTERS & OPERATIONS RESEARCH, 2024, 170
  • [49] An Application of the Local Branching to the Identical Parallel Machines Scheduling Problem
    Schimidt, T.
    Scarpin, C.
    Loch, G.
    da Silva, N.
    IEEE LATIN AMERICA TRANSACTIONS, 2019, 17 (06) : 1047 - 1054
  • [50] Parallel solutions for preemptive makespan scheduling on two identical machines
    Epstein, Leah
    JOURNAL OF SCHEDULING, 2023, 26 (01) : 61 - 76
12345