# American Institute of Mathematical Sciences

• Previous Article
Algorithms for bicriteria minimization in the permutation flow shop scheduling problem
• JIMO Home
• This Issue
• Next Article
Reliability optimization of component assignment problem for a multistate network in terms of minimal cuts
January  2011, 7(1): 229-251. doi: 10.3934/jimo.2011.7.229

## New heuristics for solving the economic lot scheduling problem with reworks

 1 Department of Information Management, Tunghai University, Taichung, Taiwan 2 Department of Transportation Technology and Management, National Chiao Tung University, Hsinchu

Received  December 2009 Revised  November 2010 Published  January 2011

In this study, we are interested in the economic lot scheduling problem (ELSP) that considers manufacturing of the serviceable products and remanufacturing of the rework products. In this paper, we formulate a mathematical model for the ELSP with reworks using the common cycle approach in which only one manufacturing lot and only one rework lot for each product exist during a common cycle. In order to solve this problem, we propose two heuristics that not only search for the optimal cycle time and an optimal production sequence, but also utilize a simple scheduling heuristic to schedule the starting time of all the manufacturing and rework lots so as to minimize the average total costs. The first heuristic is a simple heuristic that employs a 2-opt search to obtain a close-to-optimal production sequence. The second heuristic, which is a refined version of the simple heuristic, employs a bisection search to look for an optimal cycle time. In our numerical experiments, we compare the effectiveness of both heuristics using randomly generated instances.
Citation: Yu-Jen Chang, Ming-Jong Yao. New heuristics for solving the economic lot scheduling problem with reworks. Journal of Industrial & Management Optimization, 2011, 7 (1) : 229-251. doi: 10.3934/jimo.2011.7.229
##### References:
 [1] M. Barad and D. Braha, Control limits for multi-stage manufacturing processes with binomial yield (single and multiple production runs), Journal of the Operational Research Society, 47 (1996), 98-112. Google Scholar [2] F. F. Boctor, The g-group heuristic for single machine lot scheduling, International Journal of Production Research, 25 (1987), 363-379. doi: 10.1080/00207548708919847.  Google Scholar [3] E. Bomberger, A dynamic programming approach to a lot size scheduling problem, Management Science, 12 (1966), 778-784. doi: 10.1287/mnsc.12.11.778.  Google Scholar [4] U. Buscher and G. Lindner, Optimizing a production system with rework and equal sized batch shipments, Computers & Operations Research, 34 (2007), 515-535. doi: 10.1016/j.cor.2005.03.011.  Google Scholar [5] J. J. Carreno, Economic lot scheduling for multiple products on parallel identical processors, Management Science, 36 (1990), 348-358. doi: 10.1287/mnsc.36.3.348.  Google Scholar [6] S. W. Chiu, C.-K. Ting and Y.-S. P. Chiu, Optimal production lot sizing with rework, scrap rate and service level constraint, Mathematical and Computer Modelling, 46 (2007), 535-549. doi: 10.1016/j.mcm.2006.11.031.  Google Scholar [7] S. E. Elmaghraby, The economic lot scheduling problem (ELSP): Review and extension, Management Science, 24 (1978), 587-597. doi: 10.1287/mnsc.24.6.587.  Google Scholar [8] S. D. P. Flapper, J. C. Fransoo, R. A. C. M. Broekmeulen and K. Inderfurth, Planning and control of rework in the process industries: A review, Production Planning & Control, 13 (2002), 26-34. doi: 10.1080/09537280110061548.  Google Scholar [9] B. Golany, J. Yang and G. Yu, Economic lot-sizing with remanufacturing options, IIE Transactions, 33 (2001), 995-1003. doi: 10.1080/07408170108936890.  Google Scholar [10] A. Grosfeld-Nir and Y. Gerchak, Multistage production to order with rework capability, Management Science, 48 (2002), 652-664. doi: 10.1287/mnsc.48.5.652.7802.  Google Scholar [11] J. Grznar and C. Riggle, An optimal algorithm for the basic period approach to the economic lot scheduling problem, International Journal of Management Science, 25 (1997), 355-364. Google Scholar [12] F. Hanssmann, "Operations Research in Production and Inventory," Johnson Wiley & Sons, NY, 1962. Google Scholar [13] W. L. Hsu, On the general feasibility of scheduling lot sizes of several products on one machine, Management Science, 29 (1983), 93-105. doi: 10.1287/mnsc.29.1.93.  Google Scholar [14] K. Inderfurth, S. D. P. Flapper, A. J. D. Lambert, C. P. Pappis and T. G. Voutsinas, Production planning for product recovery management, in "Reverse Logistics-Quantitative Models for Closed-Loop Supply Chains" (R. Dekker, M. Fleischmann, K. Inderfurth and L. N. van Wassenhove eds), Springer, (2004), 249-274. Google Scholar [15] M. Khouja, The economic lot and delivery scheduling problem: common cycle, rework, and variable production rate, IIE Transactions, 32 (2000), 715-725. doi: 10.1080/07408170008967429.  Google Scholar [16] H. L. Lee, Lot sizing to reduce capacity utilization in a production process with defective items, process corrections and rework, Management Science, 38 (1992), 1314-1328. doi: 10.1287/mnsc.38.9.1314.  Google Scholar [17] H. L. Lee and M. J. Rosenblatt, Simultaneous determination of production cycle and inspection schedules in a production system, Management Science, 33 (1987), 1125-1136. doi: 10.1287/mnsc.33.9.1125.  Google Scholar [18] M. A. Lopez and B. G. Kingsmans, The economic lot scheduling problem: Theory and practice. International Journal of Production Economics, 23 (1991), 147-164. doi: 10.1016/0925-5273(91)90058-2.  Google Scholar [19] I. Moon, E. A. Silver and S. Choi, Hybrid genetic algorithm for the economic lot-scheduling problem, International Journal of Production Research, 40 (2002), 809-824. doi: 10.1080/00207540110095222.  Google Scholar [20] E. L. Porteus, Optimal lot sizing, process quality improvement and setup cost reduction, Operations Research, 34 (1986), 137-44. doi: 10.1287/opre.34.1.137.  Google Scholar [21] E. L. Porteus, The impact of inspection delay on process and inspection lot sizing, Management Science, 36 (1990), 999-1007. doi: 10.1287/mnsc.36.8.999.  Google Scholar [22] K. Richter, The EOQ and waste disposal model with variable setup numbers, European Journal of Operational Research, 95 (1996), 313-324. doi: 10.1016/0377-2217(95)00276-6.  Google Scholar [23] K. Richter, The extended EOQ repair and waste disposal model, International Journal of Production Economics, 45 (1996), 443-448. doi: 10.1016/0925-5273(95)00143-3.  Google Scholar [24] D. A. Schrady, A deterministic inventory model for repairable items, Naval Research Logistics Quarterly, 14 (1967), 391-398. doi: 10.1002/nav.3800140310.  Google Scholar [25] O. Tang and R. H. Teunter, Economic lot scheduling problems with returns, Production and Operations Management, 15 (2006), 488-497. doi: 10.1111/j.1937-5956.2006.tb00158.x.  Google Scholar [26] R. H. Teunter, Economic ordering quantities for recoverable Item inventory systems, Naval Research Logistics, 48 (2001), 484-495. doi: 10.1002/nav.1030.  Google Scholar [27] R. H. Teunter, Lot-sizing for inventory systems with product recovery, Computers & Industrial Engineering, 46 (2004), 431-441. doi: 10.1016/j.cie.2004.01.006.  Google Scholar [28] R. H. Teunter, Z. P. Bayindir and W. V. D. Heuvel, Dynamic lot sizing with product returns and remanufacturing, International Journal of Production Research, 44 (2006), 4377-4400. doi: 10.1080/00207540600693564.  Google Scholar [29] R. H. Teunter, K. Kaparis and O. Tang, Multu-product economic lot scheduling problem with separate production lines for manufacturing and remanufacturing, European Journal of Operational Research, 191 (2008), 1241-1253. doi: 10.1016/j.ejor.2007.08.003.  Google Scholar [30] R. H. Teunter, O. Tang and K. Kaparis, Heuristics for the economic lot scheduling problem with returns, International Journal of Production Economics, 118 (2009), 323-330. doi: 10.1016/j.ijpe.2008.08.036.  Google Scholar [31] A. S. Wein, Random yield, rework and scrap in a multistage batch manufacturing environment, Operations Research, 40 (1992), 551-563. doi: 10.1287/opre.40.3.551.  Google Scholar [32] W. L. Winston, "Operations Research Applications and Algorithms," PWS-Kent Publishing Company, Boston, 1991. Google Scholar [33] C. A. Yano and H. L. Lee, Lot sizing with random yields: A review, Operations Research, 43 (1995), 311-334. doi: 10.1287/opre.43.2.311.  Google Scholar [34] M. J. Yao, "The Economic Lot Scheduling Problem with Extension to Multiple Resource Constraints," Unpublished PhD thesis, North Carolina State University, USA, 1999. Google Scholar [35] M. J. Yao, S. E. Elmaghraby and I. C. Chen, On the feasibility testing of the economic lot scheduling problem using the extended basic period approach, Journal of the Chinese Institute of Industrial Engineering, 20 (2003), 435-448. doi: 10.1080/10170660309509249.  Google Scholar

show all references

##### References:
 [1] M. Barad and D. Braha, Control limits for multi-stage manufacturing processes with binomial yield (single and multiple production runs), Journal of the Operational Research Society, 47 (1996), 98-112. Google Scholar [2] F. F. Boctor, The g-group heuristic for single machine lot scheduling, International Journal of Production Research, 25 (1987), 363-379. doi: 10.1080/00207548708919847.  Google Scholar [3] E. Bomberger, A dynamic programming approach to a lot size scheduling problem, Management Science, 12 (1966), 778-784. doi: 10.1287/mnsc.12.11.778.  Google Scholar [4] U. Buscher and G. Lindner, Optimizing a production system with rework and equal sized batch shipments, Computers & Operations Research, 34 (2007), 515-535. doi: 10.1016/j.cor.2005.03.011.  Google Scholar [5] J. J. Carreno, Economic lot scheduling for multiple products on parallel identical processors, Management Science, 36 (1990), 348-358. doi: 10.1287/mnsc.36.3.348.  Google Scholar [6] S. W. Chiu, C.-K. Ting and Y.-S. P. Chiu, Optimal production lot sizing with rework, scrap rate and service level constraint, Mathematical and Computer Modelling, 46 (2007), 535-549. doi: 10.1016/j.mcm.2006.11.031.  Google Scholar [7] S. E. Elmaghraby, The economic lot scheduling problem (ELSP): Review and extension, Management Science, 24 (1978), 587-597. doi: 10.1287/mnsc.24.6.587.  Google Scholar [8] S. D. P. Flapper, J. C. Fransoo, R. A. C. M. Broekmeulen and K. Inderfurth, Planning and control of rework in the process industries: A review, Production Planning & Control, 13 (2002), 26-34. doi: 10.1080/09537280110061548.  Google Scholar [9] B. Golany, J. Yang and G. Yu, Economic lot-sizing with remanufacturing options, IIE Transactions, 33 (2001), 995-1003. doi: 10.1080/07408170108936890.  Google Scholar [10] A. Grosfeld-Nir and Y. Gerchak, Multistage production to order with rework capability, Management Science, 48 (2002), 652-664. doi: 10.1287/mnsc.48.5.652.7802.  Google Scholar [11] J. Grznar and C. Riggle, An optimal algorithm for the basic period approach to the economic lot scheduling problem, International Journal of Management Science, 25 (1997), 355-364. Google Scholar [12] F. Hanssmann, "Operations Research in Production and Inventory," Johnson Wiley & Sons, NY, 1962. Google Scholar [13] W. L. Hsu, On the general feasibility of scheduling lot sizes of several products on one machine, Management Science, 29 (1983), 93-105. doi: 10.1287/mnsc.29.1.93.  Google Scholar [14] K. Inderfurth, S. D. P. Flapper, A. J. D. Lambert, C. P. Pappis and T. G. Voutsinas, Production planning for product recovery management, in "Reverse Logistics-Quantitative Models for Closed-Loop Supply Chains" (R. Dekker, M. Fleischmann, K. Inderfurth and L. N. van Wassenhove eds), Springer, (2004), 249-274. Google Scholar [15] M. Khouja, The economic lot and delivery scheduling problem: common cycle, rework, and variable production rate, IIE Transactions, 32 (2000), 715-725. doi: 10.1080/07408170008967429.  Google Scholar [16] H. L. Lee, Lot sizing to reduce capacity utilization in a production process with defective items, process corrections and rework, Management Science, 38 (1992), 1314-1328. doi: 10.1287/mnsc.38.9.1314.  Google Scholar [17] H. L. Lee and M. J. Rosenblatt, Simultaneous determination of production cycle and inspection schedules in a production system, Management Science, 33 (1987), 1125-1136. doi: 10.1287/mnsc.33.9.1125.  Google Scholar [18] M. A. Lopez and B. G. Kingsmans, The economic lot scheduling problem: Theory and practice. International Journal of Production Economics, 23 (1991), 147-164. doi: 10.1016/0925-5273(91)90058-2.  Google Scholar [19] I. Moon, E. A. Silver and S. Choi, Hybrid genetic algorithm for the economic lot-scheduling problem, International Journal of Production Research, 40 (2002), 809-824. doi: 10.1080/00207540110095222.  Google Scholar [20] E. L. Porteus, Optimal lot sizing, process quality improvement and setup cost reduction, Operations Research, 34 (1986), 137-44. doi: 10.1287/opre.34.1.137.  Google Scholar [21] E. L. Porteus, The impact of inspection delay on process and inspection lot sizing, Management Science, 36 (1990), 999-1007. doi: 10.1287/mnsc.36.8.999.  Google Scholar [22] K. Richter, The EOQ and waste disposal model with variable setup numbers, European Journal of Operational Research, 95 (1996), 313-324. doi: 10.1016/0377-2217(95)00276-6.  Google Scholar [23] K. Richter, The extended EOQ repair and waste disposal model, International Journal of Production Economics, 45 (1996), 443-448. doi: 10.1016/0925-5273(95)00143-3.  Google Scholar [24] D. A. Schrady, A deterministic inventory model for repairable items, Naval Research Logistics Quarterly, 14 (1967), 391-398. doi: 10.1002/nav.3800140310.  Google Scholar [25] O. Tang and R. H. Teunter, Economic lot scheduling problems with returns, Production and Operations Management, 15 (2006), 488-497. doi: 10.1111/j.1937-5956.2006.tb00158.x.  Google Scholar [26] R. H. Teunter, Economic ordering quantities for recoverable Item inventory systems, Naval Research Logistics, 48 (2001), 484-495. doi: 10.1002/nav.1030.  Google Scholar [27] R. H. Teunter, Lot-sizing for inventory systems with product recovery, Computers & Industrial Engineering, 46 (2004), 431-441. doi: 10.1016/j.cie.2004.01.006.  Google Scholar [28] R. H. Teunter, Z. P. Bayindir and W. V. D. Heuvel, Dynamic lot sizing with product returns and remanufacturing, International Journal of Production Research, 44 (2006), 4377-4400. doi: 10.1080/00207540600693564.  Google Scholar [29] R. H. Teunter, K. Kaparis and O. Tang, Multu-product economic lot scheduling problem with separate production lines for manufacturing and remanufacturing, European Journal of Operational Research, 191 (2008), 1241-1253. doi: 10.1016/j.ejor.2007.08.003.  Google Scholar [30] R. H. Teunter, O. Tang and K. Kaparis, Heuristics for the economic lot scheduling problem with returns, International Journal of Production Economics, 118 (2009), 323-330. doi: 10.1016/j.ijpe.2008.08.036.  Google Scholar [31] A. S. Wein, Random yield, rework and scrap in a multistage batch manufacturing environment, Operations Research, 40 (1992), 551-563. doi: 10.1287/opre.40.3.551.  Google Scholar [32] W. L. Winston, "Operations Research Applications and Algorithms," PWS-Kent Publishing Company, Boston, 1991. Google Scholar [33] C. A. Yano and H. L. Lee, Lot sizing with random yields: A review, Operations Research, 43 (1995), 311-334. doi: 10.1287/opre.43.2.311.  Google Scholar [34] M. J. Yao, "The Economic Lot Scheduling Problem with Extension to Multiple Resource Constraints," Unpublished PhD thesis, North Carolina State University, USA, 1999. Google Scholar [35] M. J. Yao, S. E. Elmaghraby and I. C. Chen, On the feasibility testing of the economic lot scheduling problem using the extended basic period approach, Journal of the Chinese Institute of Industrial Engineering, 20 (2003), 435-448. doi: 10.1080/10170660309509249.  Google Scholar
 [1] Axel Kohnert, Johannes Zwanzger. New linear codes with prescribed group of automorphisms found by heuristic search. Advances in Mathematics of Communications, 2009, 3 (2) : 157-166. doi: 10.3934/amc.2009.3.157 [2] Javad Taheri, Abolfazl Mirzazadeh. Optimization of inventory system with defects, rework failure and two types of errors under crisp and fuzzy approach. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021068 [3] Ömer Arslan, Selçuk Kürşat İşleyen. A model and two heuristic methods for The Multi-Product Inventory-Location-Routing Problem with heterogeneous fleet. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021002 [4] Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703 [5] Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030 [6] Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071 [7] Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029 [8] Yukang He, Zhengwen He, Nengmin Wang. Tabu search and simulated annealing for resource-constrained multi-project scheduling to minimize maximal cash flow gap. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2451-2474. doi: 10.3934/jimo.2020077 [9] Xiaohui Lyu, Nengmin Wang, Zhen Yang, Haoxun Chen. Shipper collaboration in forward and reverse logistics. Journal of Industrial & Management Optimization, 2020, 16 (2) : 669-705. doi: 10.3934/jimo.2018173 [10] Mahdi Karimi, Seyed Jafar Sadjadi, Alireza Ghasemi Bijaghini. An economic order quantity for deteriorating items with allowable rework of deteriorated products. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1857-1879. doi: 10.3934/jimo.2018126 [11] Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial & Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457 [12] Ata Allah Taleizadeh, Solaleh Sadat Kalantari, Leopoldo Eduardo Cárdenas-Barrón. Determining optimal price, replenishment lot size and number of shipments for an EPQ model with rework and multiple shipments. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1059-1071. doi: 10.3934/jimo.2015.11.1059 [13] Mingyong Lai, Hongming Yang, Songping Yang, Junhua Zhao, Yan Xu. Cyber-physical logistics system-based vehicle routing optimization. Journal of Industrial & Management Optimization, 2014, 10 (3) : 701-715. doi: 10.3934/jimo.2014.10.701 [14] Nan Liu, Yong Ye. Humanitarian logistics planning for natural disaster response with Bayesian information updates. Journal of Industrial & Management Optimization, 2014, 10 (3) : 665-689. doi: 10.3934/jimo.2014.10.665 [15] Michelle L.F. Cheong, Rohit Bhatnagar, Stephen C. Graves. Logistics network design with supplier consolidation hubs and multiple shipment options. Journal of Industrial & Management Optimization, 2007, 3 (1) : 51-69. doi: 10.3934/jimo.2007.3.51 [16] Kemal Kilic, Menekse G. Saygi, Semih O. Sezer. Exact and heuristic methods for personalized display advertising in virtual reality platforms. Journal of Industrial & Management Optimization, 2019, 15 (2) : 833-854. doi: 10.3934/jimo.2018073 [17] Chia-Huang Wu, Kuo-Hsiung Wang, Jau-Chuan Ke, Jyh-Bin Ke. A heuristic algorithm for the optimization of M/M/$s$ queue with multiple working vacations. Journal of Industrial & Management Optimization, 2012, 8 (1) : 1-17. doi: 10.3934/jimo.2012.8.1 [18] Yuzhong Zhang, Chunsong Bai, Qingguo Bai, Jianteng Xu. Duplicating in batch scheduling. Journal of Industrial & Management Optimization, 2007, 3 (4) : 685-692. doi: 10.3934/jimo.2007.3.685 [19] Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2020, 16 (1) : 103-115. doi: 10.3934/jimo.2018142 [20] Cheng-Kang Chen, Yi-Xiang Liao. A deteriorating inventory model for an intermediary firm under return on inventory investment maximization. Journal of Industrial & Management Optimization, 2014, 10 (4) : 989-1000. doi: 10.3934/jimo.2014.10.989

2020 Impact Factor: 1.801

## Metrics

• PDF downloads (76)
• HTML views (0)
• Cited by (2)

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]