A three-stage method with efficient calculation for lot streaming flow-shop scheduling

Hai-yan WANG; Fu ZHAO; Hui-min GAO; John W. SUTHERLAND

doi:10.1631/FITEE.1700457

Your Location：

Home >

Browse articles >

A three-stage method with efficient calculation for lot streaming flow-shop scheduling

Regular Papers | Updated：2022-05-19

- A three-stage method with efficient calculation for lot streaming flow-shop scheduling
- 一种流水车间批量调度的高效计算三阶段优化方法
- Frontiers of Information Technology & Electronic Engineering Vol. 20, Issue 7, Pages: 1002-1020(2019)
- Affiliations：
  
  College of Mechanical and Electrical Engineering, Jiaxing University, Jiaxing 314000, China
  Environmental and Ecological Engineering, Purdue University, West Lafayette, IN 47907, USA
  School of Mechanical Engineering, Purdue University, West Lafayette, IN 47907, USA
- Author bio：
  
  Hai-yan WANG, E-mail: wanghy@mail.zjxu.edu.cn
- Funds：
- DOI：10.1631/FITEE.1700457
  CLC： TH166;TP278
- Received：09 July 2017，
  
  Revised：2019-;7-;3，
  
  Published：2019-07
- Accepted：
Scan QR Code
Hai-yan WANG, Fu ZHAO, Hui-min GAO, et al. A three-stage method with efficient calculation for lot streaming flow-shop scheduling[J]. Frontiers of Information Technology & Electronic Engineering, 2019, 20(7): 1002-1020.
DOI：

Hai-yan WANG, Fu ZHAO, Hui-min GAO, et al. A three-stage method with efficient calculation for lot streaming flow-shop scheduling[J]. Frontiers of Information Technology & Electronic Engineering, 2019, 20(7): 1002-1020. DOI： 10.1631/FITEE.1700457.

摘要

在工件含批量生产任务情况下如何进行最佳生产调度是一个重要的生产计划问题。通常将批量工件划分为子批处理（称为分批优化）。若子批数较大，则会大大增加工件完成时间的计算复杂性。现有研究未能考虑此类计算时间问题。本文考虑可变子批、准备时间以及子批批量约束（传输子批批量受传输设备容量限制），提出一种求解

个工件、

台机器流水车间分批优化调度方法。所提方法包含3个阶段：初始批量划分、基于生产周期/总流程时间指标快速评价法的工件排序优化、分批传输方案调整。为验证3阶段优化方法的有效性，采用5个标准数据集进行测试。实验结果表明，所提方法能节省大量计算时间，尤其对大规模问题能提供更优解。

Abstract

An important production planning problem is how to best schedule jobs (or lots) when each job consists of a large number of identical parts. This problem is often approached by breaking each job/lot into sublots (termed lot streaming). When the total number of transfer sublots in lot streaming is large

the computational effort to calculate job completion time can be significant. However

researchers have largely neglected this computation time issue. To provide a practical method for production scheduling for this situation

we propose a method to address the

-job

-machine

and lot streaming flow-shop scheduling problem. We consider the variable sublot sizes

setup time

and the possibility that transfer sublot sizes may be bounded because of capacity constrained transportation activities. The proposed method has three stages: initial lot splitting

job sequencing optimization with efficient calculation of the makespan/total flow time criterion

and transfer adjustment. Computational experiments are conducted to confirm the effectiveness of the three-stage method. The experiments reveal that relative to results reported on lot streaming problems for five standard datasets

the proposed method saves substantial computation time and provides better solutions

especially for large-size problems.

关键词

Keywords

references

KR Baker . . Lot streaming in the two-machine flow shop with setup times . . Ann Oper Res , , 1995 . . 57 ( ( 1 ): ): 1 - - 11 . . DOI: 10.1007/BF02099687 http://doi.org/10.1007/BF02099687 . .

D Biskup , , , M Feldmann . . Lot streaming with variable sublots: an integer programming formulation . . J Oper Res Soc , , 2006 . . 57 ( ( 3 ): ): 296 - - 303 . . DOI: 10.1057/palgrave.jors.2602016 http://doi.org/10.1057/palgrave.jors.2602016 . .

GV Chakaravarthy , , , S Marimuthu , , , AN Sait . . Performance evaluation of proposed differential evolution and particle swarm optimization algorithms for scheduling m-machine flow shops with lot streaming . . J Intell Manuf , , 2013 . . 24 ( ( 1 ): ): 175 - - 191 . . DOI: 10.1007/s10845-011-0552-2 http://doi.org/10.1007/s10845-011-0552-2 . .

GV Chakaravarthy , , , S Marimuthu , , , SG Ponnambalam , , , 等 . . Improved sheep flock heredity algorithm and artificial bee colony algorithm for scheduling m -machine flow shops lot streaming with equal size sub-lot problems . . Int J Prod Res , , 2014 . . 52 ( ( 5 ): ): 1509 - - 1527 . . DOI: 10.1080/00207543.2013.848304 http://doi.org/10.1080/00207543.2013.848304 . .

M Cheng , , , NJ Mukherjee , , , SC Sarin . . A review of lot streaming . . Int J Prod Res , , 2013 . . 51 ( ( 23-24 ): ): 7023 - - 7046 . . DOI: 10.1080/00207543.2013.774506 http://doi.org/10.1080/00207543.2013.774506 . .

D Davendra , , , R Senkerik , , , I Zelinka , , , 等 . . Utilising the chaos-induced discrete self organising migrating algorithm to solve the lot-streaming flowshop scheduling problem with setup time . . Soft Comput , , 2014 . . 18 ( ( 4 ): ): 669 - - 681 . . DOI: 10.1007/s00500-014-1219-7 http://doi.org/10.1007/s00500-014-1219-7 . .

FM Defersha , , , MY Chen . . A hybrid genetic algorithm for flowshop lot streaming with setups and variable sublots . . Int J Prod Res , , 2010 . . 48 ( ( 6 ): ): 1705 - - 1726 . . DOI: 10.1080/00207540802660544 http://doi.org/10.1080/00207540802660544 . .

FM Defersha , , , MY Chen . . A genetic algorithm for one-job m-machine flowshop lot streaming with variable sublots . . Int J Oper Res , , 2011 . . 10 ( ( 4 ): ): 458 - - 468 . . DOI: 10.1504/IJOR.2011.039713 http://doi.org/10.1504/IJOR.2011.039713 . .

YY Han , , , DW Gong , , , YC Jin , , , 等 . . Evolutionary multiobjective blocking lot-streaming flow shop scheduling with interval processing time . . Appl Soft Comput , , 2016 . . 42 229 - - 245 . . DOI: 10.1016/j.asoc.2016.01.033 http://doi.org/10.1016/j.asoc.2016.01.033 . .

K Kim , , , IJ Jeong . . Flow shop scheduling with no-wait flexible lot streaming using an adaptive genetic algorithm . . Int J Adv Manuf Technol , , 2009 . . 44 ( ( 11-12 ): ): 1181 - - 1190 . . DOI: 10.1007/s00170-007-1236-0 http://doi.org/10.1007/s00170-007-1236-0 . .

S Kumar , , , TP Bagchi , , , C Sriskandarajah . . Lot streaming and scheduling heuristics for m -machine no-wait flowshops . . Comput Ind Eng , , 2000 . . 38 ( ( 1 ): ): 149 - - 172 . . DOI: 10.1016/S0360-8352(00)00035-8 http://doi.org/10.1016/S0360-8352(00)00035-8 . .

JY Liu . . Single-job lot streaming in m -1 two-stage hybrid flowshops . . Eur J Oper Res , , 2008 . . 187 ( ( 3 ): ): 1171 - - 1183 . . DOI: 10.1016/j.ejor.2006.06.066 http://doi.org/10.1016/j.ejor.2006.06.066 . .

SC Liu . . A heuristic method for discrete lot streaming with variable sublots in a flow shop . . Int J Adv Manuf Technol , , 2003 . . 22 ( ( 9-10 ): ): 662 - - 668 . . DOI: 10.1007/s00170-002-1516-7 http://doi.org/10.1007/s00170-002-1516-7 . .

S Marimuthu , , , SG Ponnambalam , , , N Jawahar . . Evolutionary algorithms for scheduling m -machine flow shop with lot streaming . . Robot Comput Integr Manuf , , 2008 . . 24 ( ( 1 ): ): 125 - - 139 . . DOI: 10.1016/j.rcim.2006.06.007 http://doi.org/10.1016/j.rcim.2006.06.007 . .

S Marimuthu , , , SG Ponnambalam , , , N Jawahar . . Threshold accepting and ant-colony optimization algorithms for scheduling m -machine flow shops with lot streaming . . J Mater Process Technol , , 2009 . . 209 ( ( 2 ): ): 1026 - - 1041 . . DOI: 10.1016/j.jmatprotec.2008.03.013 http://doi.org/10.1016/j.jmatprotec.2008.03.013 . .

CH Martin . . A hybrid genetic algorithm/mathematical programming approach to the multi-family flowshop scheduling problem with lot streaming . . Omega , , 2009 . . 37 ( ( 1 ): ): 126 - - 137 . . DOI: 10.1016/j.omega.2006.11.002 http://doi.org/10.1016/j.omega.2006.11.002 . .

NJ Mukherjee , , , SC Sarin , , , S Singh . . Lot streaming in the presence of learning in sublot-attached setup times and processing times . . Int J Prod Res , , 2017 . . 55 ( ( 6 ): ): 1623 - - 1639 . . DOI: 10.1080/00207543.2016.1200760 http://doi.org/10.1080/00207543.2016.1200760 . .

M Nejati , , , I Mahdavi , , , R Hassanzadeh , , , 等 . . Multi-job lot streaming to minimize the weighted completion time in a hybrid flow shop scheduling problem with work shift constraint . . Int J Adv Manuf Technol , , 2014 . . 70 ( ( 1-4 ): ): 501 - - 514 . . DOI: 10.1007/s00170-013-5265-6 http://doi.org/10.1007/s00170-013-5265-6 . .

M Nejati , , , I Mahdavi , , , R Hassanzadeh , , , 等 . . Lot streaming in a two-stage assembly hybrid flow shop scheduling problem with a work shift constraint . . J Ind Prod Eng , , 2016 . . 33 ( ( 7 ): ): 459 - - 471 . . DOI: 10.1080/21681015.2015.1126653 http://doi.org/10.1080/21681015.2015.1126653 . .

G Onwubolu , , , D Davendra . . Scheduling flow shops using differential evolution algorithm . . Eur J Oper Res , , 2006 . . 171 ( ( 2 ): ): 674 - - 692 . . DOI: 10.1016/j.ejor.2004.08.043 http://doi.org/10.1016/j.ejor.2004.08.043 . .

QK Pan , , , PN Suganthan , , , JJ Liang , , , 等 . . A local-best harmony search algorithm with dynamic sub-harmony memories for lot-streaming flow shop scheduling problem . . Expert Syst Appl , , 2011 . . 38 ( ( 4 ): ): 3252 - - 3259 . . DOI: 10.1016/j.eswa.2010.08.111 http://doi.org/10.1016/j.eswa.2010.08.111 . .

S Reiter . . A system for managing job-shop production . . J Bus , , 1966 . . 39 ( ( 3 ): ): 371 - - 393 . . DOI: 10.1086/294867 http://doi.org/10.1086/294867 . .

SC Sarin , , , AA Kalir , , , M Chen . . A single-lot, unified cost-based flow shop lot-streaming problem . . Int J Prod Econ , , 2008 . . 113 ( ( 1 ): ): 413 - - 424 . . DOI: 10.1016/j.ijpe.2007.10.002 http://doi.org/10.1016/j.ijpe.2007.10.002 . .

R Storn , , , K Price . . Differential evolutionja simple and efficient adaptive scheme for global optimization over continuous spaces . . J Glob Optim , , 1997 . . 11 ( ( 4 ): ): 341 - - 359 . . DOI: 10.1023/a:1008202821328 http://doi.org/10.1023/a:1008202821328 . .

MF Tasgetiren , , , QK Pan , , , PN Suganthan , , , 等 . . A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem . . Comput Oper Res , , 2013 . . 40 ( ( 7 ): ): 1729 - - 1743 . . DOI: 10.1016/j.cor.2013.01.005 http://doi.org/10.1016/j.cor.2013.01.005 . .

CT Tseng , , , CJ Liao . . A discrete particle swarm optimization for lot-streaming flowshop scheduling problem . . Eur J Oper Res , , 2008 . . 191 ( ( 2 ): ): 360 - - 373 . . DOI: 10.1016/j.ejor.2007.08.030 http://doi.org/10.1016/j.ejor.2007.08.030 . .

JA Ventura , , , SH Yoon . . A new genetic algorithm for lot-streaming flow shop scheduling with limited capacity buffers . . J Intell Manuf , , 2013 . . 24 ( ( 6 ): ): 1185 - - 1196 . . DOI: 10.1007/s10845-012-0650-9 http://doi.org/10.1007/s10845-012-0650-9 . .

L Wang , , , QK Pan , , , PN Suganthan , , , 等 . . A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems . . Comput Oper Res , , 2010 . . 37 ( ( 3 ): ): 509 - - 520 . . DOI: 10.1016/j.cor.2008.12.004 http://doi.org/10.1016/j.cor.2008.12.004 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Differential evolution based computation intelligence solver for elliptic partial differential equations

Detecting faulty sensors in an array using symmetrical structure and cultural algorithm hybridized with differential evolution

An improved chaotic hybrid differential evolution for the short-term hydrothermal scheduling problem considering practical constraints

Related Author

Muhammad Faisal FATEH

Aneela ZAMEER

Sikander M. MIRZA

Nasir M. MIRZA

Muhammad Saeed ASLAM

Muhammad Asif Zahoor RAJA

Shafqat Ullah KHAN

Ijaz Mansoor QURESHI

Related Institution

Department of Electrical Engineering, Pakistan Institute of Engineering and Applied Sciences (PIEAS)

Department of Computer and Information Sciences, Pakistan Institute of Engineering and Applied Sciences (PIEAS)

Department of Physics and Applied Mathematics, Pakistan Institute of Engineering and Applied Sciences (PIEAS)

School of Electrical and Electronic Engineering, University of Adelaide

Department of Electrical and Computer Engineering, COMSATS University Islamabad, Attock Campus, Attock

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰