An iterative heuristic for the single machine dynamic total completion time scheduling problem

被引：14
|
作者：
Chand, S
Traub, R
Uzsoy, R
机构：
[1] UNIV IOWA,COLL BUSINESS ADM,IOWA CITY,IA 52242
[2] PURDUE UNIV,SCH IND ENGN,W LAFAYETTE,IN 47907
来源：
COMPUTERS & OPERATIONS RESEARCH | 1996年 / 23卷 / 07期
关键词：
D O I：
10.1016/0305-0548(95)00071-2
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
We address the problem of scheduling a single machine to minimize the total completion time in the face of dynamic job arrivals. Since the problem is strongly NP-hard, considerable research has been devoted to examining one-pass heuristic procedures for this problem. In this paper we present an iterative improvement heuristic which operates by modifying the problem data in a manner that allows one-pass heuristics to generate improved solutions. Computational experiments show that the procedure obtains significant improvements over a variety of one-pass heuristics in modest CPU times. Copyright (C) 1996 Elsevier Science Ltd
引用
收藏
页码：641 / 651
页数：11
相关论文
共 50 条
  • [1] Iterative heuristic for the single machine dynamic total completion time scheduling problem
    Purdue Univ, West Lafayette, United States
    Comput Oper Res, 7 (641-651):
  • [2] Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time
    Batsyn, Mikhail
    Goldengorin, Boris
    Pardalos, Panos M.
    Sukhov, Pavel
    OPTIMIZATION METHODS & SOFTWARE, 2014, 29 (05): : 955 - 963
  • [3] Scheduling Single Machine Problem to Minimize Completion Time
    Suppiah, Yasothei
    Bhuvaneswari, Thangavel
    Yee, Pang Shen
    Yue, Ng Wei
    Horng, Chan Mun
    TEM JOURNAL-TECHNOLOGY EDUCATION MANAGEMENT INFORMATICS, 2022, 11 (02): : 552 - 556
  • [4] A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem
    Ocetkiewicz, Krzysztof M.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 203 (02) : 316 - 320
  • [5] Single Machine Scheduling Problem with Interval Processing Times and Total Completion Time Objective
    Sotskov, Yuri N.
    Egorova, Natalja G.
    ALGORITHMS, 2018, 11 (05)
  • [6] Minimizing the total completion time in a single-machine scheduling problem with a learning effect
    Low, Chinyao
    Lin, Wen-Yi
    APPLIED MATHEMATICAL MODELLING, 2011, 35 (04) : 1946 - 1951
  • [7] Improving the preemptive bound for the one-machine dynamic total completion time scheduling problem
    Della Croce, F
    T'kindt, V
    OPERATIONS RESEARCH LETTERS, 2003, 31 (02) : 142 - 148
  • [8] An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints
    Sadfi, C
    Penz, B
    Rapine, C
    Blazewicz, J
    Formanowicz, P
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2005, 161 (01) : 3 - 10
  • [9] Single machine total completion time scheduling problem with workload-dependent maintenance duration
    Xu, Dehua
    Wan, Long
    Liu, Aihua
    Yang, Dar-Li
    OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2015, 52 : 101 - 106
  • [10] Simple heuristic to minimize total tardiness in a single machine scheduling problem
    Panneerselvam, R.
    International Journal of Advanced Manufacturing Technology, 2006, 30 (7-8): : 722 - 726
12345