带时间窗口的自动化混流生产线调度方法

工业工程 ›› 2011, Vol. 14 ›› Issue (5): 110-115.

带时间窗口的自动化混流生产线调度方法

西北工业大学管理学院，陕西西安 710072

出版日期:2011-10-31 发布日期:2011-11-11
作者简介:雷卫东（1985-），男，陕西省人，博士研究生，主要研究方向为工业工程.
基金资助:
国家自然科学基金资助项目（50605052、71071129）;教育部“新世纪优秀人才支持计划”（NCET-06-0875）

Scheduling Algorithm for Automated Mixed Production Line with Time Window Constraint

School of Management, Northwestern Polytechnical University, Xi’an, 710072, China

Online:2011-10-31 Published:2011-11-11

摘要/Abstract

摘要： 研究了一类带时间窗口的自动化混流生产线调度问题，其中包括工件排序和机器人搬运作业排序两类问题。在对问题进行系统分析的基础上，考虑处理时间窗口约束、机器人搬运能力约束和工作站能力约束，使用混合整数规划方法建立了此类问题的通用数学模型，并采用CPLEX软件求解模型，以印刷电路板电镀生产线为实例并通过随机算例验证该方法的有效性。

关键词: 自动化混流生产线, 周期性调度, 混合整数规划, 时间窗口

Abstract: The scheduling problem for a class of automated mixed production line with time window constraint is discussed. For such a system, it should sequence both the jobs and the robot movements. Based on a systematic analysis, in considering time window constraint on job processing times, robot availability constraint, and resource capability constraint, the problem is formulated as a mixed integer programming model. Then, the commercial software CPLEX is used to solve it. Computational results on benchmark and randomly generated instances show that the proposed MIP approach is very efficient in scheduling the automated mixed production line.

Key words: automated mixed production line, cyclic scheduling, mixed integer programming, time window constraint

雷卫东，车阿大 . 带时间窗口的自动化混流生产线调度方法[J]. 工业工程, 2011, 14(5): 110-115.

Lei Weidong, Che Ada. Scheduling Algorithm for Automated Mixed Production Line with Time Window Constraint[J]. Industrial Engineering Journal , 2011, 14(5): 110-115.

参考文献

［1］Dawande M，Geismar H N，Sethi S P，et al. Sequencing and scheduling in robotic cells: recent development ［J］. Journal of Scheduling，2005，8(5):387-426. ［2］Che A，Chu C. Multidegree cyclic scheduling of a no wait robotic cell with multiple robots ［J］. European Journal of Operation Research，2009，199(1): 77-88. ［3］Leung J，Zhang G. Optimal cyclic scheduling for printed circuitboard production lines with multiple hoists and general processing sequences［J］. IEEE Transactions on Robotics and Automation 2003，19(3): 480-484. ［4］Lei L，Wang T J. A proof: the cyclic hoist scheduling problem is NP-hard ［R］. New Jersey，USA: Rutgers University，1989. ［5］Chen H，Chu C，Proth J M. Cyclic scheduling of a hoist with time window constraints ［J］. IEEE Transactions on Robotics and Automation，1998，14(1): 144-152.［6］Yan P，Chu C，Yang N，et al. A branch and bound algorithm for Optimal Cyclic Scheduling in a Robotic Cell with Processing Time windows ［J］. International Journal of Production Research，2010，48(21): 6461-6480. ［7］李鹏，车阿大. 基于混沌遗传算法的自动化生产单元调度方法研究［J］.系统工程,2008,26(11):75-80. ［8］Liu J，Jiang Y，Zhou Z. Cyclic scheduling of a single hoist in extended electroplating lines: a comprehensive integer programming solution ［J］. IIE Transactions，2002，34(10): 905-914.  ［9］Che A，Chu C. Cyclic hoist scheduling in large reallife electroplating lines ［J］. OR Spectrum，2007，29(3): 445-470. ［10］Lei L，Liu Q. Optimal cyclic scheduling of a robotic processing line with twoproduct and timewindow constraints ［J］. INFOR，2001，39(2): 185-199. ［11］Amraoui A E，Manier A M，Moudni A E，et al. A mixed linear problem for a multipart cyclic hoist scheduling problem ［J］. International Journal Science and Techniques of Automatic & Computer Engineering，2008,2(special issue): 612-623.

[1]	温馨，丁一，林国龙. 考虑内陆转运的集装箱班轮运输网络设计方法[J]. 工业工程, 2015, 18(2): 121-126.
[2]	米传民，夏卫国，强媛. 基于灰关联和模糊规划的产品设计改进方法[J]. 工业工程, 2014, 17(3): 97-100.
[3]	乐美龙，檀财茂. 非正常运行下机场停机位实时分配模型[J]. 工业工程, 2014, 17(1): 12-16.