Grid Branch-and-Bound for Permutation Flowshop

被引:0
|
作者
Drozdowski, Maciej [1 ]
Marciniak, Pawel [1 ]
Pawlak, Grzegorz [1 ]
Plaza, Maciej [1 ]
机构
[1] Poznan Univ Tech, Inst Comp Sci, PL-60965 Poznan, Poland
来源
PARALLEL PROCESSING AND APPLIED MATHEMATICS, PT II | 2012年 / 7204卷
关键词
branch-and-bound; flowshop; grid computing; SCHEDULING PROBLEMS; SEQUENCING PROBLEM; ALGORITHMS;
D O I
暂无
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Flowshop is an example of a classic hard combinatorial problem. Branch-and-bound is a technique commonly used for solving such hard problems. Together, the two can be used as a benchmark of maturity of parallel processing environment. Grid systems pose a number of hurdles which must be overcome in practical applications. We give a report on applying parallel branch-and-bound for flowshop in grid environment. Methods dealing with the complexities of the environment and the application are proposed, and evaluated.
引用
收藏
页码:21 / 30
页数:10
相关论文
共 50 条
  • [21] A computationally efficient Branch-and-Bound algorithm for the permutation flow-shop scheduling problem
    Gmys, Jan
    Mezmaz, Mohand
    Melab, Nouredine
    Tuyttens, Daniel
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2020, 284 (03) : 814 - 833
  • [22] Branch-and-bound algorithm for permutation flow shops with sequence-dependent setup times
    Ríos-Mercado, Roger Z.
    Bard, Jonathan F.
    IIE Transactions (Institute of Industrial Engineers), 1999, 31 (08): : 721 - 731
  • [23] Branch-and-bound algorithms on a hypercube
    Pargas, R.P.
    Wooster, D.E.
    Conference on Hypercube Concurrent Computers and Applications, 1988,
  • [24] AND/OR Branch-and-Bound for Graphical Models
    Marinescu, Radu
    Dechter, Rina
    19TH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI-05), 2005, : 224 - 229
  • [25] BRANCH-AND-BOUND PROGRAM GENERATOR
    NOLTEMEIER, H
    COMPUTING, 1971, 8 (1-2) : 99 - +
  • [26] Compressing Branch-and-Bound Trees
    Munoz, Gonzalo
    Paat, Joseph
    Xavier, Alinson S.
    INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2023, 2023, 13904 : 348 - 362
  • [27] PROBLEMS UNSOLVABLE BY BRANCH-AND-BOUND
    JEROSLOW, RG
    NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY, 1973, 20 (04): : A440 - A441
  • [28] A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems
    Chung, Chia-Shin
    Flynn, James
    Kirca, Omer
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 174 (01) : 1 - 10
  • [29] BRANCH-AND-BOUND METHODS - A SURVEY
    LAWLER, EL
    WOOD, DE
    OPERATIONS RESEARCH, 1966, 14 (04) : 699 - +
  • [30] A NOTE ON BRANCH-AND-BOUND PRINCIPLE
    BALAS, E
    OPERATIONS RESEARCH, 1968, 16 (02) : 442 - &