Interval-indexed formulation based heuristics for single machine total weighted tardiness problem

被引：6

作者：

Altunc, Arife Burcu Colak ^{[1
]}

Keha, Ahmet Burak ^{[1
]}

机构：

[1] Arizona State Univ, Dept Ind Engn, Tempe, AZ 85287 USA

来源：

COMPUTERS & OPERATIONS RESEARCH | 2009年 / 36卷 / 06期

关键词：

Single machine scheduling; Interval-indexed formulation; Mixed integer programming; Linear programming based heuristics; AVERAGE COMPLETION-TIME; SCHEDULING PROBLEMS; ALGORITHM; MINIMIZE; COSTS; OPTIMIZATION;

D O I：

10.1016/j.cor.2008.08.004

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

in this paper, we solve the single machine total weighted tardiness problem by using integer programming and linear programming based heuristic algorithms. Interval-indexed formulation is used to formulate the problem. We discuss several methods to form the intervals and different post-processing methods. Then, we show how our algorithm can be used to improve a population of a genetic algorithm. We also provide some computational results that show the effectiveness of our algorithm. Many aspects of our heuristic algorithm are quite general and can be applied to other scheduling and combinatorial optimization problems. (C) 2008 Elsevier Ltd. All rights reserved.

引用

页码：2122 / 2131

页数：10

共 50 条

[31] Heuristics for the single machine weighted sum of completion times scheduling problem with periodic maintenance
Krim, Hanane
Benmansour, Rachid
Duvivier, David
Ait-Kadi, Daoud
Hanafi, Said
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2020, 75 (01) : 291 - 320
[32] Greedy randomised dispatching heuristics for the single machine scheduling problem with quadratic earliness and tardiness penalties
Valente, Jorge M. S.
Moreira, Maria R. A.
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2009, 44 (9-10) : 995 - 1009
[33] Hybrid heuristics for the single machine scheduling problem with quadratic earliness and tardiness costs
Alok Singh
Jorge M. S. Valente
Maria R. A. Moreira
International Journal of Machine Learning and Cybernetics, 2012, 3 : 327 - 333
[34] A Novel Ant Colony Algorithm for the Single-Machine Total Weighted Tardiness Problem with Sequence Dependent Setup Times
Ahmadizar, Fardin
Hosseini, Leila
INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE SYSTEMS, 2011, 4 (04): : 456 - 466
[35] Hybrid heuristics for the single machine scheduling problem with quadratic earliness and tardiness costs
Singh, Alok
Valente, Jorge M. S.
Moreira, Maria R. A.
INTERNATIONAL JOURNAL OF MACHINE LEARNING AND CYBERNETICS, 2012, 3 (04) : 327 - 333
[36] Distributed Quantum Annealing on D-Wave for the Single Machine Total Weighted Tardiness Scheduling Problem
Bozejko, Wojciech
Pempera, Jaroslaw
Uchronski, Mariusz
Wodecki, Mieczyslaw
COMPUTATIONAL SCIENCE, ICCS 2022, PT IV, 2022, : 171 - 178
[37] On heuristic search for the single machine total weighted tardiness problem - Some theoretical insights and their empirical verification
Geiger, Martin Josef
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 207 (03) : 1235 - 1243
[38] A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date
Kellerer, Hans
Strusevich, Vitaly A.
THEORETICAL COMPUTER SCIENCE, 2006, 369 (1-3) : 230 - 238
[39] Single CNC machine scheduling with controllable processing times to minimize total weighted tardiness
Akturk, M. Selim
Ilhan, Taylan
COMPUTERS & OPERATIONS RESEARCH, 2011, 38 (04) : 771 - 781
[40] Algorithmic paradoxes of the single-machine total tardiness problem
Szwarc, W
Grosso, A
Della Croce, F
JOURNAL OF SCHEDULING, 2001, 4 (02) : 93 - 104

← 1 2 3 4 5 →