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 条
  • [21] Lunar cycle inspired PSO for single machine total weighted tardiness scheduling problem
    Gupta, Shruti
    Kumari, Rajani
    Singh, Rishi Pal
    EVOLUTIONARY INTELLIGENCE, 2021, 14 (03) : 1355 - 1366
  • [22] Parallel Algorithm with Blocks for a Single-Machine Total Weighted Tardiness Scheduling Problem
    Uchronski, Mariusz
    APPLIED SCIENCES-BASEL, 2021, 11 (05): : 1 - 17
  • [23] A discrete electromagnetism-like mechanism for single machine total weighted tardiness problem with sequence-dependent setup times
    Chao, Chien-Wen
    Liao, Ching-Jong
    APPLIED SOFT COMPUTING, 2012, 12 (09) : 3079 - 3087
  • [24] An Iterated Local Search heuristic for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times
    Subramanian, Anand
    Battarra, Maria
    Potts, Chris N.
    INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2014, 52 (09) : 2729 - 2742
  • [25] New insights on the single machine total tardiness problem
    Tansel, BC
    Sabuncuoglu, I
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1997, 48 (01) : 82 - 89
  • [26] Solving the Single Machine Total Weighted Tardiness Problem Using Bat-Inspired Algorithm
    Kongkaew, Wanatchapong
    2015 IEEE INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT (IEEM), 2015, : 265 - 269
  • [27] A Simplified Scatter Search for a Special Single Machine Scheduling Problem to Minimize Total Weighted Tardiness
    Wang, Xianpeng
    Tang, Lixin
    PROCEEDINGS OF THE 48TH IEEE CONFERENCE ON DECISION AND CONTROL, 2009 HELD JOINTLY WITH THE 2009 28TH CHINESE CONTROL CONFERENCE (CDC/CCC 2009), 2009, : 6250 - 6255
  • [28] Single Machine Weighted Tardiness Problem: An Algorithm and Experimentation System
    Petrynski, Kacper
    Szost, Robert
    Pozniak-Koszalka, Iwona
    Koszalka, Leszek
    Kasprzak, Andrzej
    COMPUTATIONAL COLLECTIVE INTELLIGENCE, ICCCI 2018, PT II, 2018, 11056 : 36 - 44
  • [29] Parallel branch-and-price algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times
    Speckenmeyer, Philipp
    Hilmer, Constanze
    Rauchecker, Gerhard
    Schryen, Guido
    COMPUTERS & OPERATIONS RESEARCH, 2025, 173
  • [30] Weighted tardiness for the single machine scheduling problem: An examination of precedence theorem productivity
    Kanet, J. J.
    Birkemeier, C.
    COMPUTERS & OPERATIONS RESEARCH, 2013, 40 (01) : 91 - 97
12345