Autosoft Journal

Online Manuscript Access


On the use of genetic algorithm for solving re-entrant flowshop scheduling with sum-of-processing-times-based learning effect to minimize the total tardiness


Authors



Abstract

Most research studies on scheduling problems assume that a job visits certain machines only one time. However, this assumption is invalid in some real-life situations. For example, a job may be processed by the same machine more than once in semiconductor wafer manufacturing or in a printed circuit board manufacturing machine. Such a setting is known as the “re-entrant flowshop”. On the other hand, the importance of learning effect present in many practical situations such as machine shop, in different branches of industry and for a variety of corporate activities, in shortening life cycles, and in an increasing diversity of products in the manufacturing environment. Inspired by these observations, this paper addresses a re-entrant m-machine flowshop scheduling problems with time-dependent learning effect to minimize the total tardiness. The complexity of the proposed problem is very difficult. Therefore, in this paper we first present four heuristic algorithms, which are modified from existing algorithms to solve the problem. Then, we use the solutions as four initials to a genetic algorithm. Finally, we report experimental performances of all the proposed methods for the small and big numbers of jobs, respectively.


Keywords


Pages

Total Pages: 11

DOI
10.1080/10798587.2017.1302711


Manuscript ViewPdf Subscription required to access this document

Obtain access this manuscript in one of the following ways


Already subscribed?

Need information on obtaining a subscription? Personal and institutional subscriptions are available.

Already an author? Have access via email address?


Published

Online Article

Cite this document


References

Alfieri, A. "Workload Simulation and Optimisation in Multi-Criteria Hybrid Flowshop Scheduling: a Case Study." International Journal of Production Research 47.18 (2009): 5129-5145. Crossref. Web. https://doi.org/10.1080/00207540802010823

Bellman R. Mathematical aspects of scheduling and applications

BENGÜ, G. "A Simulation-Based Scheduler for Flexible Flowlines." International Journal of Production Research 32.2 (1994): 321-344. Crossref. Web. https://doi.org/10.1080/00207549408956936

Biskup, Dirk. "Single-Machine Scheduling with Learning Considerations." European Journal of Operational Research 115.1 (1999): 173-178. Crossref. Web. https://doi.org/10.1016/S0377-2217(98)00246-X

Biskup, Dirk. "A State-of-the-Art Review on Scheduling with Learning Effects." European Journal of Operational Research 188.2 (2008): 315-329. Crossref. Web. https://doi.org/10.1016/j.ejor.2007.05.040

Bispo C.F. IIE Transaction

Boudhar, Mourad, and Nadjat Meziani. "Two-Stage Hybrid Flow Shop with Recirculation." International Transactions in Operational Research 17.2 (2010): 239-255. Crossref. Web. https://doi.org/10.1111/j.1475-3995.2009.00711.x

Chen, Jen-Shiang. "A Branch and Bound Procedure for the Reentrant Permutation Flow-Shop Scheduling Problem." The International Journal of Advanced Manufacturing Technology 29.11-12 (2005): 1186-1193. Crossref. Web. https://doi.org/10.1007/s00170-005-0017-x

Chen, Chuen-Lung, Venkateswara S. Vempati, and Nasser Aljaber. "An Application of Genetic Algorithms for Flow Shop Problems." European Journal of Operational Research 80.2 (1995): 389-396. Crossref. Web. https://doi.org/10.1016/0377-2217(93)E0228-P

Chen, Jen-Shiang, Jason Chao-Hsien Pan, and Chien-Kuang Wu. "Minimizing Makespan in Reentrant Flow-Shops Using Hybrid Tabu Search." The International Journal of Advanced Manufacturing Technology 34.3-4 (2006): 353-361. Crossref. Web. https://doi.org/10.1007/s00170-006-0607-2

Cheng M. Mathematical Problems in Engineering

Cheng, T.C. Edwin, and Guoqing Wang. Annals of Operations Research 98.1/4 (2000): 273-290. Crossref. Web. https://doi.org/10.1023/A:1019216726076

Cheng, T.C.E. et al. "Two-Machine Flowshop Scheduling with a Truncated Learning Function to Minimize the Makespan." International Journal of Production Economics 141.1 (2013): 79-86. Crossref. Web. https://doi.org/10.1016/j.ijpe.2012.03.027

Choi, Seong-Woo, and Yeong-Dae Kim. "Minimizing Total Tardiness on a Two-Machine Re-Entrant Flowshop." European Journal of Operational Research 199.2 (2009): 375-384. Crossref. Web. https://doi.org/10.1016/j.ejor.2008.11.037

Chu, Feng, Chengbin Chu, and Caroline Desprez. "Series Production in a Basic Re-Entrant Shop to Minimize Makespan or Total Flow Time." Computers & Industrial Engineering 58.2 (2010): 257-268. Crossref. Web. https://doi.org/10.1016/j.cie.2009.02.017

Chung, Yu-Hsiang, and Lee-Ing Tong. "Bi-Criteria Minimization for the Permutation Flowshop Scheduling Problem with Machine-Based Learning Effects." Computers & Industrial Engineering 63.1 (2012): 302-312. Crossref. Web. https://doi.org/10.1016/j.cie.2012.03.009

Etiler O. Journal Inst. Technology, Gazi University, Turkey

Etiler, O et al. "A Genetic Algorithm for Flow Shop Scheduling Problems." Journal of the Operational Research Society 55.8 (2004): 830-835. Crossref. Web. https://doi.org/10.1057/palgrave.jors.2601766

Higgins P. Manufacturing planning and control-beyond MRP II

Janiak A. Decision Making in Manufacturing

Koulamas, Christos. "The Total Tardiness Problem: Review and Extensions." Operations Research 42.6 (1994): 1025-1041. Crossref. Web. https://doi.org/10.1287/opre.42.6.1025

Kubiak, Wieslaw, Sheldon X. C. Lou, and Yingmeng Wang. "Mean Flow Time Minimization in Reentrant Job Shops with a Hub." Operations Research 44.5 (1996): 764-776. Crossref. Web. https://doi.org/10.1287/opre.44.5.764

Kuo, Wen-Hung, Chou-Jung Hsu, and Dar-Li Yang. "Worst-Case and Numerical Analysis of Heuristic Algorithms for Flowshop Scheduling Problems with a Time-Dependent Learning Effect." Information Sciences 184.1 (2012): 282-297. Crossref. Web. https://doi.org/10.1016/j.ins.2011.08.018

Danping, Lin, and Carman K.M. Lee. "A Review of the Research Methodology for the Re-Entrant Scheduling Problem." International Journal of Production Research 49.8 (2010): 2221-2242. Crossref. Web. https://doi.org/10.1080/00207541003720350

Liu, Cheng-Hsiang. "A Genetic Algorithm Based Approach for Scheduling of Jobs Containing Multiple Orders in a Three-Machine Flowshop." International Journal of Production Research 48.15 (2009): 4379-4396. Crossref. Web. https://doi.org/10.1080/00207540902933163

NADLER, G., and W. D. SMITH. "MANUFACTURING PROGRESS FUNCTIONS FOR TYPES OF PROCESSES." International Journal of Production Research 2.2 (1963): 115-135. Crossref. Web. https://doi.org/10.1080/00207546308947818

Nawaz, Muhammad, E Emory Enscore, and Inyong Ham. "A Heuristic Algorithm for the m-Machine, n-Job Flow-Shop Sequencing Problem." Omega 11.1 (1983): 91-95. Crossref. Web. https://doi.org/10.1016/0305-0483(83)90088-9

Pan, JC-H, and J-S Chen. "Minimizing Makespan in Re-Entrant Permutation Flow-Shops." Journal of the Operational Research Society 54.6 (2003): 642-653. Crossref. Web. https://doi.org/10.1057/palgrave.jors.2601556

Rau, Hsin, and Kuo-Hua Cho. "Genetic Algorithm Modeling for the Inspection Allocation in Reentrant Production Systems." Expert Systems with Applications 36.8 (2009): 11287-11295. Crossref. Web. https://doi.org/10.1016/j.eswa.2009.03.020

Sule D.R. Industrial scheduling

UZSOY, REHA, CHUNG-YEE LEE, and LOUIS A. MARTIN-VEGA. "A REVIEW OF PRODUCTION PLANNING AND SCHEDULING MODELS IN THE SEMICONDUCTOR INDUSTRY PART I: SYSTEM CHARACTERISTICS, PERFORMANCE EVALUATION AND PRODUCTION PLANNING." IIE Transactions 24.4 (1992): 47-60. Crossref. Web. https://doi.org/10.1080/07408179208964233

Vargas-Villamil, Felipe D., and Daniel E. Rivera. "A Model Predictive Control Approach for Real-Time Optimization of Reentrant Manufacturing Lines." Computers in Industry 45.1 (2001): 45-57. Crossref. Web. https://doi.org/10.1016/S0166-3615(01)00080-X

Wang, J-B. "Single-Machine Scheduling with a Sum-of-Actual-Processing-Time-Based Learning Effect." Journal of the Operational Research Society 61.1 (2010): 172-177. Crossref. Web. https://doi.org/10.1057/jors.2008.146

Wang, Ji-Bo, and Qian Guo. "A Due-Date Assignment Problem with Learning Effect and Deteriorating Jobs." Applied Mathematical Modelling 34.2 (2010): 309-313. Crossref. Web. https://doi.org/10.1016/j.apm.2009.04.020

Wang J.B. Journal of the Operational Research Society https://doi.org/10.1057/jors.2011.40

Wang, J-B, and Z-Q Xia. "Flow-Shop Scheduling with a Learning Effect." Journal of the Operational Research Society 56.11 (2005): 1325-1330. Crossref. Web. https://doi.org/10.1057/palgrave.jors.2601856

Wang, M. Y., S. P. Sethi, and S. L. van de Velde. "Minimizing Makespan in a Class of Reentrant Shops." Operations Research 45.5 (1997): 702-712. Crossref. Web. https://doi.org/10.1287/opre.45.5.702

Wang, Xiao-Yuan et al. "Several Flow Shop Scheduling Problems with Truncated Position-Based Learning Effect." Computers & Operations Research 40.12 (2013): 2906-2929. Crossref. Web. https://doi.org/10.1016/j.cor.2013.07.001

Wu, Chin-Chia, and Wen-Chiung Lee. "A Note on the Total Completion Time Problem in a Permutation Flowshop with a Learning Effect." European Journal of Operational Research 192.1 (2009): 343-347. Crossref. Web. https://doi.org/10.1016/j.ejor.2007.10.003

Wu, Chin-Chia et al. "Re-Entrant Flowshop Scheduling With Learning Considerations to Minimize The Makespan." Iranian Journal of Science and Technology, Transactions A: Science 42.2 (2017): 727-744. Crossref. Web. https://doi.org/10.1007/s40995-017-0236-7

Xu, Yuming et al. "A Genetic Algorithm for Task Scheduling on Heterogeneous Computing Systems Using Multiple Priority Queues." Information Sciences 270 (2014): 255-287. Crossref. Web. https://doi.org/10.1016/j.ins.2014.02.122

Xu, Jianyou et al. "Heuristic Based Genetic Algorithms for the Re-Entrant Total Completion Time Flowshop Scheduling with Learning Consideration." International Journal of Computational Intelligence Systems 9.6 (2016): 1082-1100. Crossref. Web. https://doi.org/10.1080/18756891.2016.1256572

Yang, S-J, and D-L Yang. "Single-Machine Scheduling Problems with Past-Sequence-Dependent Delivery Times and Position-Dependent Processing Times." Journal of the Operational Research Society 63.11 (2012): 1508-1515. Crossref. Web. https://doi.org/10.1057/jors.2011.155

Yang, Suh-Jenq, Chou-Jung Hsu, and Dar-Li Yang. "Parallel-Machine Scheduling with Setup and Removal Times Under Consideration of the Learning Effect." Journal of the Chinese Institute of Industrial Engineers 27.5 (2010): 372-378. Crossref. Web. https://doi.org/10.1080/10170669.2010.503040

Yelle, Louis E. "THE LEARNING CURVE: HISTORICAL REVIEW AND COMPREHENSIVE SURVEY." Decision Sciences 10.2 (1979): 302-328. Crossref. Web. https://doi.org/10.1111/j.1540-5915.1979.tb00026.x

Yin, Na, and Xiao-Yuan Wang. "Single-Machine Scheduling with Controllable Processing Times and Learning Effect." The International Journal of Advanced Manufacturing Technology 54.5-8 (2010): 743-748. Crossref. Web. https://doi.org/10.1007/s00170-010-2973-z

Yin, Yunqiang et al. "Some Scheduling Problems with General Position-Dependent and Time-Dependent Learning Effects." Information Sciences 179.14 (2009): 2416-2425. Crossref. Web. https://doi.org/10.1016/j.ins.2009.02.015

Yin, Yunqiang, Dehua Xu, and Jiayin Wang. "Some Single-Machine Scheduling Problems with Past-Sequence-Dependent Setup Times and a General Learning Effect." The International Journal of Advanced Manufacturing Technology 48.9-12 (2009): 1123-1132. Crossref. Web. https://doi.org/10.1007/s00170-009-2360-9

Yin, Yunqiang, Dehua Xu, and Jiayin Wang. "Single-Machine Scheduling with a General Sum-of-Actual-Processing-Times-Based and Job-Position-Based Learning Effect." Applied Mathematical Modelling 34.11 (2010): 3623-3630. Crossref. Web. https://doi.org/10.1016/j.apm.2010.03.011

Yin, Yunqiang, Dehua Xu, and Jiayin Wang. "Single-Machine Scheduling with a General Sum-of-Actual-Processing-Times-Based and Job-Position-Based Learning Effect." Applied Mathematical Modelling 34.11 (2010): 3623-3630. Crossref. Web. https://doi.org/10.1016/j.apm.2010.03.011

Zhang, Xingong et al. "Single-Machine Scheduling Problems with a Learning Effect Matrix." Iranian Journal of Science and Technology, Transactions A: Science 42.3 (2016): 1327-1335. Crossref. Web. https://doi.org/10.1007/s40995-016-0080-1

JOURNAL INFORMATION


ISSN PRINT: 1079-8587
ISSN ONLINE: 2326-005X
DOI PREFIX: 10.31209
10.1080/10798587 with T&F
IMPACT FACTOR: 0.652 (2017/2018)
Journal: 1995-Present




CONTACT INFORMATION


TSI Press
18015 Bullis Hill
San Antonio, TX 78258 USA
PH: 210 479 1022
FAX: 210 479 1048
EMAIL: tsiepress@gmail.com
WEB: http://www.wacong.org/tsi/