2.765

2022影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

批处理机上具有两类释放时间的工件集竞争调度问题

赵晓丽 宫华 车平

赵晓丽, 宫华, 车平. 批处理机上具有两类释放时间的工件集竞争调度问题. 自动化学报, 2020, 46(1): 168-177. doi: 10.16383/j.aas.2018.c170536
引用本文: 赵晓丽, 宫华, 车平. 批处理机上具有两类释放时间的工件集竞争调度问题. 自动化学报, 2020, 46(1): 168-177. doi: 10.16383/j.aas.2018.c170536
ZHAO Xiao-Li, GONG Hua, CHE Ping. The Competing Job Sets Scheduling Problems With Two Types of Release Dates on Batching-Machine. ACTA AUTOMATICA SINICA, 2020, 46(1): 168-177. doi: 10.16383/j.aas.2018.c170536
Citation: ZHAO Xiao-Li, GONG Hua, CHE Ping. The Competing Job Sets Scheduling Problems With Two Types of Release Dates on Batching-Machine. ACTA AUTOMATICA SINICA, 2020, 46(1): 168-177. doi: 10.16383/j.aas.2018.c170536

批处理机上具有两类释放时间的工件集竞争调度问题

doi: 10.16383/j.aas.2018.c170536
基金项目: 

国家自然科学基金项目 71402021

辽宁省科技厅自然科学基金计划重点项目 20170540790

沈阳市科技计划项目 17231131

详细信息
    作者简介:

    宫华  博士, 沈阳理工大学理学院教授.主要研究方向为生产调度, 物流优化. E-mail: gonghua1018@sina.com

    车平  博士, 东北大学理学院数学系讲师.主要研究方向为发电调度, 生产计划, 生产调度.E-mail: cheping@mail.neu.edu.cn

    通讯作者:

    赵晓丽  博士, 沈阳航空航天大学理学院讲师.主要研究方向为生产调度与组合优化.本文通信作者. E-mail: zhaoxiaoli824@163.com

The Competing Job Sets Scheduling Problems With Two Types of Release Dates on Batching-Machine

Funds: 

National Natural Science Foundation of China 71402021

Key Natural Science Foundation Project of Liaoning Province 20170540790

Science and Technology Project of Shenyang City 17231131

More Information
    Author Bio:

    GONG Hua  Ph. D., professor at the School of Science, Shenyang Ligong University. Her research interest covers production scheduling and logistics optimization

    CHE Ping  Ph. D., lecturer in the Department of Mathematics, College of Sciences, Northeastern University. Her research interest covers generation scheduling, production planning, and production scheduling

    Corresponding author: ZHAO Xiao-Li  Ph. D., lecturer at the School of Science, Shenyang Aerospace University. Her research interest covers production scheduling and combinational optimization. Corresponding author of this paper
  • 摘要: 研究了两个工件集合竞争在一台批处理机上加工的调度问题, 其中每个集合的工件具有一个共同的释放时间.批处理机可以同时加工多个工件作为一批, 每批的加工时间为该批工件中加工时间的最大值.基于两类释放时间的大小, 针对无界批处理机上最小化一个集合工件的最大完工时间、最大延迟以及总完工时间, 使得另一个集合工件的最大完工时间不超过给定上界问题, 分别给出了最优求解方法.针对有界批处理机上最小化一个集合工件的最大完工时间, 使得另一个集合工件的最大完工时间不超过给定上界问题, 证明为一般意义NP--!难问题, 并给出伪多项式时间最优求解方法.
    Recommended by Associate Editor QIAO Jun-Fei
    1)  本文责任编委  乔俊飞
  • 图  1  钢铁工业钢锭初轧过程

    Fig.  1  Ingot rolling process in the steel industry

    图  2  最优调度$\pi$

    Fig.  2  The optimal schedule $\pi$

    图  3  最优调度$\pi'$

    Fig.  3  The optimal schedule $\pi'$

  • [1] Baker K R, Smith J C. A multiple-criterion model for machine scheduling. Journal of Scheduling, 2003, 6(1): 7-16 doi: 10.1023/A:1022231419049
    [2] Agnetis A, Mirchandani P B, Pacciarelli D, Pacifici A. Scheduling problems with two competing agents. Operations Research, 2004, 52(2): 229-242 doi: 10.1287/opre.1030.0092
    [3] Perez-Gonzalez P, Framinan J M. A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: multi-agent scheduling problems. European Journal of Operational Research, 2014, 235(1): 1-16 http://cn.bing.com/academic/profile?id=d83ba5b1366d427e307f2996e67e39a1&encoded=0&v=paper_preview&mkt=zh-cn
    [4] Agnetis A, Billaut J C, Gawiejnowicz S, Pacciarelli D, Soukhal A. Multiagent Scheduling: Models and Algorithms. Heidelberg: Springer, 2014.
    [5] Li S S, Yuan J J. Unbounded parallel-batching scheduling with two competitive agents. Journal of Scheduling, 2012, 15(5): 629-640 doi: 10.1007/s10951-011-0253-x
    [6] Fan B Q, Cheng T C E, Li S S, Feng Q. Bounded parallel-batching scheduling with two competing agents. Journal of Scheduling, 2013, 16(3): 261-271 doi: 10.1007/s10951-012-0274-0
    [7] Wang J Q, Fan G Q, Zhang Y Q, Zhang C W, Leung J Y T. Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes. European Journal of Operational Research, 2017, 258(2): 478-490 doi: 10.1016/j.ejor.2016.10.024
    [8] Tang L X, Zhao X L, Liu J Y, Leung J Y T. Competitive two-agent scheduling with deteriorating jobs on a single parallel-batching machine. European Journal of Operational Research, 2017, 263(2): 401-411 doi: 10.1016/j.ejor.2017.05.019
    [9] Yin Y Q, Wu W H, Cheng S R, Wu C C. An investigation on a two-agent single-machine scheduling problem with unequal release dates. Computers & Operations Research, 2012, 39(12): 3062-3073 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=a9a59b2f6984e4385a5c3da81206fd84
    [10] Lee W C, Chung Y H, Hu M C. Genetic algorithms for a two-agent single-machine problem with release time. Applied Soft Computing, 2012, 12(11): 3580-3589 doi: 10.1016/j.asoc.2012.06.015
    [11] Wu C C, Wu W H, Chen J C, Yin Y Q, Wu W H. A study of the single-machine two-agent scheduling problem with release times. Applied Soft Computing, 2013, 13(2): 998-1006 doi: 10.1016/j.asoc.2012.10.003
    [12] Cheng T C E, Chung Y H, Liao S C, Lee W C. Two-agent singe-machine scheduling with release times to minimize the total weighted completion time. Computers & Operations Research, 2013, 40(1): 353-361 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=30b2aab966d975e2914462ee77a86bc1
    [13] Dover O, Shabtay D. Single machine scheduling with two competing agents, arbitrary release dates and unit processing times. Annals of Operations Research, 2016, 238(1-2): 145-178 doi: 10.1007/s10479-015-2054-7
    [14] Potts C N, Kovalyov M Y. Scheduling with batching: a review. European Journal of Operational Research, 2000, 120(2): 228-249 doi: 10.1016/S0377-2217(99)00153-8
    [15] Brucker P, Gladky A, Hoogeveen H, Kovalyov M Y, Potts C N, Tautenhahn T, et al. Scheduling a batching machine. Journal of Scheduling, 1998, 1(1): 31-54 doi: 10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R
    [16] Lee C Y. Minimizing makespan on a single batch processing machine with dynamic job arrivals. International Journal of Production Research, 1999, 37(1): 219-236 doi: 10.1080/002075499192020
    [17] Liu Z H, Yu W C. Scheduling one batch processor subject to job release dates. Discrete Applied Mathematics, 2000, 105(1-3): 129-136 doi: 10.1016/S0166-218X(00)00181-5
    [18] Liu Z H, Cheng T C E. Approximation schemes for minimizing total (weighted) completion time with release dates on a batch machine. Theoretical Computer Science, 2005, 347(1-2): 288-298 doi: 10.1016/j.tcs.2005.07.028
  • 加载中
图(3)
计量
  • 文章访问数:  1481
  • HTML全文浏览量:  278
  • PDF下载量:  103
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-09-22
  • 录用日期:  2018-04-16
  • 刊出日期:  2020-01-21

目录

    /

    返回文章
    返回