A Simplified Scatter Search for a Special Single Machine Scheduling Problem to Minimize Total Weighted Tardiness

被引：0
作者：
Wang, Xianpeng [1 ]
Tang, Lixin [1 ]
机构：
[1] Northeastern Univ, Liaoning Key Lab Mfg Syst & Logist, Logist Inst, Shenyang 110004, Peoples R China
来源：
PROCEEDINGS OF THE 48TH IEEE CONFERENCE ON DECISION AND CONTROL, 2009 HELD JOINTLY WITH THE 2009 28TH CHINESE CONTROL CONFERENCE (CDC/CCC 2009) | 2009年
关键词：
VARIABLE NEIGHBORHOOD SEARCH; IDENTICAL PROCESSING TIMES; PRECEDENCE CONSTRAINTS; RELEASE DATES; ALGORITHM;
D O I：
10.1109/CDC.2009.5399647
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
This paper investigates a new kind of single machine scheduling problem derived from the production scheduling of reheating furnaces in the iron and steel industry. In this problem, the single machine can simultaneously process multiple jobs. However, there is no batch and the jobs enter and leave the machine one by one and continuously. The objective is to minimize the total weighted tardiness of all jobs. We formulate this problem as a mixed integer linear programming (MILP) model and propose a simplified scatter search algorithm. The computational results on randomly generated instances show that the MILP model is correct and the proposed SSS algorithm outperforms CPLEX.
引用
收藏
页码：6250 / 6255
页数：6
相关论文
共 18 条
  • [1] A tabu search algorithm for the single machine total weighted tardiness problem
    Bilge, Umit
    Kurtulan, Mujde
    Kirac, Furkan
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 176 (03) : 1423 - 1435
  • [2] Block approach - tabu search algorithm for single machine total weighted tardiness problern
    Bozejko, Wojciech
    Grabowski, Jozef
    Wodecki, Mieczyslaw
    [J]. COMPUTERS & INDUSTRIAL ENGINEERING, 2006, 50 (1-2) : 1 - 14
  • [3] ONE-MACHINE BATCHING AND SEQUENCING OF MULTIPLE-TYPE ITEMS
    CHENG, TCE
    CHEN, ZL
    OGUZ, C
    [J]. COMPUTERS & OPERATIONS RESEARCH, 1994, 21 (07) : 717 - 721
  • [4] Scheduling a batch-processing machine subject to precedence constraints, release dates and identical processing times
    Cheng, TCE
    Yuan, JJ
    Yang, AF
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2005, 32 (04) : 849 - 859
  • [5] An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem
    Congram, RK
    Potts, CN
    van de Velde, SL
    [J]. INFORMS JOURNAL ON COMPUTING, 2002, 14 (01) : 52 - 67
  • [6] Crauwels H. A. J., 1998, INFORMS Journal on Computing, V10, P341, DOI 10.1287/ijoc.10.3.341
  • [7] Lawler E. L., 1977, Ann. Disc. Math., V1, P331, DOI [DOI 10.1016/S0167-5060(08)70742-8, 10.1016/S0167-5060(08)70742-8]
  • [8] EFFICIENT ALGORITHMS FOR SCHEDULING SEMICONDUCTOR BURN-IN OPERATIONS
    LEE, CY
    UZSOY, R
    MARTINVEGA, LA
    [J]. OPERATIONS RESEARCH, 1992, 40 (04) : 764 - 775
  • [9] Lenstra J. K., 1977, Annals of discrete mathematics, V1, P343, DOI DOI 10.1016/S0167-5060(08)70743-X
  • [10] Scheduling in an assembly-type production chain with batch transfer
    Lin, B. M. T.
    Cheng, T. C. E.
    Chou, A. S. C.
    [J]. OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2007, 35 (02): : 143 - 151
12