Improving Column Generation Methods or Sheduling Problems Using ZDD and Stabilization

被引：0

作者：

Leus, Roel ^{[1
]}

Kowalczyk, Daniel ^{[1
]}

机构：

[1] Katholieke Univ Leuven, ORsTAr, Fac Econ & Business, Leuven, Belgium

来源：

2016 IEEE INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT (IEEM) | 2016年

关键词：

Parallel machine scheduling; weighted completion times; branch and price; ZDD; stabilization; WEIGHTED COMPLETION-TIME; PARALLEL MACHINES;

D O I：

暂无

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

In this work we tackle the parallel machine scheduling problem with identical machines to minimize the sum of weighted completion times. We study the set covering formulation for this problem that was introduced by van den Akker et al. [1], and improve the performance of their branch-and price algorithm by a number of techniques, including zero suppressed binary decision diagrams (ZDD) and stabilization. These techniques are sufficiently generic to be promising also for other scheduling problems.

引用

页码：99 / 103

页数：5

共 17 条

[1] AKERS SB, 1978, IEEE T COMPUT, V27, P509, DOI 10.1109/TC.1978.1675141
[2] [Anonymous], 1966, Management Science, DOI [10.1287/mnsc.12.5.437, DOI 10.1287/MNSC.12.5.437]
[3] On the minimization of total weighted flow time with identical and uniform parallel machines
Azizoglu, M
Kirca, O
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1999, 113 (01) : 91 - 100
[4] SCHEDULING IDENTICAL PARALLEL MACHINES TO MINIMIZE TOTAL WEIGHTED COMPLETION-TIME
BELOUADAH, H
POTTS, CN
[J]. DISCRETE APPLIED MATHEMATICS, 1994, 48 (03) : 201 - 218
[5] Brucker P., 1977, Ann. Discrete Math., V1, P343, DOI [DOI 10.1016/S0167-5060(08)70743-X, 10.1016/S0167-5060(08)70743-X]
[6] SCHEDULING INDEPENDENT TASKS TO REDUCE MEAN FINISHING TIME
BRUNO, J
COFFMAN, EG
SETHI, R
[J]. COMMUNICATIONS OF THE ACM, 1974, 17 (07) : 382 - 387
[7] Elmaghraby S. E., 1974, A I I E Transactions, V6, P1, DOI DOI 10.1080/05695557408974926
[8] Iwashita H., 2013, Tech. Rep. TCS-TR-A-13-69
[9] Knuth D.E., 2009, The Art of Computer Programming, V4
[10] FUNCTIONAL EQUATION AND ITS APPLICATION TO RESOURCE ALLOCATION AND SEQUENCING PROBLEMS
LAWLER, EL
MOORE, JM
[J]. MANAGEMENT SCIENCE SERIES A-THEORY, 1969, 16 (01): : 77 - 84

← 1 2 →