American Institute of Mathematical Sciences

Advanced
  • 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

Yu-Jen Chang 1, and  Ming-Jong Yao 2,

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.
Keywords: Inventory, rework, scheduling, logistics, heuristic, search..
Mathematics Subject Classification: Primary: 90B05; Secondary: 90B25, 90B06, 68M2.
Citation: Yu-Jen Chang, Ming-Jong Yao. New heuristics for solving the economic lot scheduling problem with reworks. Journal of Industrial and 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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[9]

B. Golany, J. Yang and G. Yu, Economic lot-sizing with remanufacturing options, IIE Transactions, 33 (2001), 995-1003. doi: 10.1080/07408170108936890.

[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.

[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.

[12]

F. Hanssmann, "Operations Research in Production and Inventory," Johnson Wiley & Sons, NY, 1962.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[24]

D. A. Schrady, A deterministic inventory model for repairable items, Naval Research Logistics Quarterly, 14 (1967), 391-398. doi: 10.1002/nav.3800140310.

[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.

[26]

R. H. Teunter, Economic ordering quantities for recoverable Item inventory systems, Naval Research Logistics, 48 (2001), 484-495. doi: 10.1002/nav.1030.

[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.

[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.

[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.

[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.

[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.

[32]

W. L. Winston, "Operations Research Applications and Algorithms," PWS-Kent Publishing Company, Boston, 1991.

[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.

[34]

M. J. Yao, "The Economic Lot Scheduling Problem with Extension to Multiple Resource Constraints," Unpublished PhD thesis, North Carolina State University, USA, 1999.

[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.

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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[9]

B. Golany, J. Yang and G. Yu, Economic lot-sizing with remanufacturing options, IIE Transactions, 33 (2001), 995-1003. doi: 10.1080/07408170108936890.

[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.

[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.

[12]

F. Hanssmann, "Operations Research in Production and Inventory," Johnson Wiley & Sons, NY, 1962.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[24]

D. A. Schrady, A deterministic inventory model for repairable items, Naval Research Logistics Quarterly, 14 (1967), 391-398. doi: 10.1002/nav.3800140310.

[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.

[26]

R. H. Teunter, Economic ordering quantities for recoverable Item inventory systems, Naval Research Logistics, 48 (2001), 484-495. doi: 10.1002/nav.1030.

[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.

[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.

[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.

[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.

[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.

[32]

W. L. Winston, "Operations Research Applications and Algorithms," PWS-Kent Publishing Company, Boston, 1991.

[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.

[34]

M. J. Yao, "The Economic Lot Scheduling Problem with Extension to Multiple Resource Constraints," Unpublished PhD thesis, North Carolina State University, USA, 1999.

[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.

[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 and Management Optimization, 2022, 18 (4) : 2289-2318. doi: 10.3934/jimo.2021068
[3]

Shengyang Jia, Lei Deng, Quanwu Zhao, Yunkai Chen. An adaptive large neighborhood search heuristic for multi-commodity two-echelon vehicle routing problem with satellite synchronization. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2021225
[4]

Ö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 and Management Optimization, 2022, 18 (2) : 897-932. doi: 10.3934/jimo.2021002
[5]

Steven Dougherty, Adrian Korban, Serap Șahinkaya, Deniz Ustun. Binary self-dual and LCD codes from generator matrices constructed from two group ring elements by a heuristic search scheme. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022036
[6]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial and Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703
[7]

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 and Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030
[8]

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 and Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071
[9]

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 and Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029
[10]

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 and Management Optimization, 2021, 17 (5) : 2451-2474. doi: 10.3934/jimo.2020077
[11]

Xiaohui Lyu, Nengmin Wang, Zhen Yang, Haoxun Chen. Shipper collaboration in forward and reverse logistics. Journal of Industrial and Management Optimization, 2020, 16 (2) : 669-705. doi: 10.3934/jimo.2018173
[12]

Mahdi Karimi, Seyed Jafar Sadjadi, Alireza Ghasemi Bijaghini. An economic order quantity for deteriorating items with allowable rework of deteriorated products. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1857-1879. doi: 10.3934/jimo.2018126
[13]

Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial and Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457
[14]

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 and Management Optimization, 2015, 11 (4) : 1059-1071. doi: 10.3934/jimo.2015.11.1059
[15]

Mingyong Lai, Hongming Yang, Songping Yang, Junhua Zhao, Yan Xu. Cyber-physical logistics system-based vehicle routing optimization. Journal of Industrial and Management Optimization, 2014, 10 (3) : 701-715. doi: 10.3934/jimo.2014.10.701
[16]

Nan Liu, Yong Ye. Humanitarian logistics planning for natural disaster response with Bayesian information updates. Journal of Industrial and Management Optimization, 2014, 10 (3) : 665-689. doi: 10.3934/jimo.2014.10.665
[17]

Michelle L.F. Cheong, Rohit Bhatnagar, Stephen C. Graves. Logistics network design with supplier consolidation hubs and multiple shipment options. Journal of Industrial and Management Optimization, 2007, 3 (1) : 51-69. doi: 10.3934/jimo.2007.3.51
[18]

Yuzhong Zhang, Chunsong Bai, Qingguo Bai, Jianteng Xu. Duplicating in batch scheduling. Journal of Industrial and Management Optimization, 2007, 3 (4) : 685-692. doi: 10.3934/jimo.2007.3.685
[19]

Kemal Kilic, Menekse G. Saygi, Semih O. Sezer. Exact and heuristic methods for personalized display advertising in virtual reality platforms. Journal of Industrial and Management Optimization, 2019, 15 (2) : 833-854. doi: 10.3934/jimo.2018073
[20]

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 and Management Optimization, 2012, 8 (1) : 1-17. doi: 10.3934/jimo.2012.8.1

2021 Impact Factor: 1.411

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy