Scheduling a flexible batching machine

被引：0
作者：
Fan, Baoqiang [1 ]
Gu, Jianzhong [1 ]
Tang, Guochun [2 ]
机构：
[1] Ludong Univ, Dept Math & Informat, Yantai 264025, Peoples R China
[2] Shanghai Second Polytechn Univ, Inst Management Engn, Shanghai 201209, Peoples R China
来源：
ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS | 2007年 / 4508卷
基金：
中国国家自然科学基金;
关键词：
scheduling; batching machine; complexity;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Minimizing total completion time Sigma Ci on normal batching machine is solvable in polynomial time for fixed B(B > 1), while Minimizing total completion time Sigma Cj for arbitrary B and minimizing total weighted completion time Sigma WjCj are open problems. In this paper, we consider the problem of scheduling jobs on a flexible batching machine in order to minimizing the total completion time. We prove that the problem is strongly NP-hard. Then the problem with agreeable is NP-hard even if there have three fixed capacities all the time.
引用
收藏
页码：91 / +
页数：3
相关论文
共 18 条
  • [1] BATCHING AND SCHEDULING JOBS ON BATCH AND DISCRETE PROCESSORS
    AHMADI, JH
    AHMADI, RH
    DASU, S
    TANG, CS
    [J]. OPERATIONS RESEARCH, 1992, 40 (04) : 750 - 763
  • [2] BRUCKER P, 1998, J SCHEDULING, V1, P131
  • [3] MINIMIZING TOTAL COMPLETION-TIME ON A BATCH PROCESSING MACHINE WITH JOB FAMILIES
    CHANDRU, V
    LEE, CY
    UZSOY, R
    [J]. OPERATIONS RESEARCH LETTERS, 1993, 13 (02) : 61 - 65
  • [4] MINIMIZING TOTAL COMPLETION-TIME ON BATCH PROCESSING MACHINES
    CHANDRU, V
    LEE, CY
    UZSOY, R
    [J]. INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 1993, 31 (09) : 2097 - 2121
  • [5] OPTIMAL SCHEDULING OF PRODUCTS WITH 2 SUBASSEMBLIES ON A SINGLE-MACHINE
    COFFMAN, EG
    NOZARI, A
    YANNAKAKIS, M
    [J]. OPERATIONS RESEARCH, 1989, 37 (03) : 426 - 436
  • [6] Fan BQ, 2006, LECT NOTES COMPUT SC, V3959, P118
  • [7] Garey M.R., 1979, COMPUTERS INTACTABIL
  • [8] Scheduling semiconductor burn-in operations to minimize total flowtime
    Hochbaum, DS
    Landy, D
    [J]. OPERATIONS RESEARCH, 1997, 45 (06) : 874 - 885
  • [9] EFFICIENT SCHEDULING ALGORITHMS FOR A SINGLE BATCH PROCESSING MACHINE
    IKURA, Y
    GIMPLE, M
    [J]. OPERATIONS RESEARCH LETTERS, 1986, 5 (02) : 61 - 65
  • [10] JULIEN F, 1989, CATCHING SCHEDULING
12