A note on the optimal makespan of a parallel machine scheduling problem

被引：0
作者：
Li, Yumei [1 ]
Gu, Yundong [2 ]
Sun, Kaibiao [3 ]
Li, Hongxing [3 ]
机构：
[1] Beijing Technol & Business Univ, Sch Informat Engn, Beijing 100037, Peoples R China
[2] N China Elect Power Univ, Sch Math & Phys, Beijing 102206, Peoples R China
[3] Beijing Normal Univ, Sch Math Sci, Beijing 100875, Peoples R China
来源：
FUZZY INFORMATION AND ENGINEERING, PROCEEDINGS | 2007年 / 40卷
基金：
中国国家自然科学基金;
关键词：
scheduling problem; parallel machine; algorithm; result schedule; optimal makespan;
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
For the parallel machine scheduling problem under consideration, the authors in two literatures of 1961 and 2002 respectively gave the proofs for the optimal makespan under Level Algorithm. But, some errors in their proofs are found by us with three counterexamples, and no one has given the correct proof until now. In this paper, a new algorithm is proposed. And the new algorithm is more convenient and easier for theoretical analysis than Level Algorithm does. Then, it is showed that the result schedule obtained by using the new algorithm is consistent with that by Level Algorithm in the sense that they can give the same result schedule. Finally, by using the proposed new algorithm, the proof for the optimal makespan is accomplished.
引用
收藏
页码：481 / +
页数：2
相关论文
共 50 条
  • [41] A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines
    Min, L
    Cheng, W
    ARTIFICIAL INTELLIGENCE IN ENGINEERING, 1999, 13 (04): : 399 - 403
  • [42] On Parallel Machine Scheduling with Rejection
    Cao, Li-si
    Liu, Zi-xian
    Jiang, Da-kui
    PROCEEDINGS OF THE 22ND INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT: CORE THEORY AND APPLICATIONS OF INDUSTRIAL ENGINEERING (VOL 1), 2016, : 845 - 851
  • [43] On-line supply chain scheduling for single-machine and parallel-machine configurations with a single customer: Minimizing the makespan and delivery cost
    Han, Bin
    Zhang, Wenjun
    Lu, Xiwen
    Lin, Yingzi
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 244 (03) : 704 - 714
  • [44] An ant colony optimization approach for the parallel machine scheduling problem with outsourcing allowed
    Tavares Neto, Roberto Fernandes
    Godinho Filho, Moacir
    da Silva, Fabio Molina
    JOURNAL OF INTELLIGENT MANUFACTURING, 2015, 26 (03) : 527 - 538
  • [45] On solving the unrelated parallel machine scheduling problem: active microrheology as a case study
    Orts, F.
    Ortega, G.
    Puertas, A. M.
    Garcia, I
    Garzon, E. M.
    JOURNAL OF SUPERCOMPUTING, 2020, 76 (11) : 8494 - 8509
  • [46] Unrelated parallel machine scheduling problem with stochastic sequence dependent setup times
    Sarac, Tugba
    Ozcelik, Feristah
    Ertem, Mehmet
    OPERATIONAL RESEARCH, 2023, 23 (03)
  • [47] Analysis of stochastic local search methods for the unrelated parallel machine scheduling problem
    Santos, Haroldo G.
    Toffolo, Tulio A. M.
    Silva, Cristiano L. T. F.
    Vanden Berghe, Greet
    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2019, 26 (02) : 707 - 724
  • [48] Research on water resources optimal scheduling problem based on parallel biological computing
    Ji, Zuwen
    Wang, Zhaocai
    Bao, Xiaoguang
    Wang, Xiaoming
    Wu, Tunhua
    DESALINATION AND WATER TREATMENT, 2018, 111 : 88 - 93
  • [49] Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems
    Min, L
    Cheng, W
    ROBOTICS AND COMPUTER-INTEGRATED MANUFACTURING, 2006, 22 (04) : 279 - 287
  • [50] Weighted earliness/tardiness parallel machine scheduling problem with a common due date
    Arik, Oguzhan Ahmet
    Schutten, Marco
    Topan, Engin
    EXPERT SYSTEMS WITH APPLICATIONS, 2022, 187
12345