• 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.   Google Scholar

[2]

F. F. Boctor, The g-group heuristic for single machine lot scheduling,, International Journal of Production Research, 25 (1987), 363.  doi: 10.1080/00207548708919847.  Google Scholar

[3]

E. Bomberger, A dynamic programming approach to a lot size scheduling problem,, Management Science, 12 (1966), 778.  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.  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.  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.  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.  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.  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.  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.  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.   Google Scholar

[12]

F. Hanssmann, "Operations Research in Production and Inventory,", Johnson Wiley & Sons, (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.  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, (2004), 249.   Google Scholar

[15]

M. Khouja, The economic lot and delivery scheduling problem: common cycle, rework, and variable production rate,, IIE Transactions, 32 (2000), 715.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  doi: 10.1287/opre.40.3.551.  Google Scholar

[32]

W. L. Winston, "Operations Research Applications and Algorithms,", PWS-Kent Publishing Company, (1991).   Google Scholar

[33]

C. A. Yano and H. L. Lee, Lot sizing with random yields: A review,, Operations Research, 43 (1995), 311.  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, (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.  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.   Google Scholar

[2]

F. F. Boctor, The g-group heuristic for single machine lot scheduling,, International Journal of Production Research, 25 (1987), 363.  doi: 10.1080/00207548708919847.  Google Scholar

[3]

E. Bomberger, A dynamic programming approach to a lot size scheduling problem,, Management Science, 12 (1966), 778.  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.  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.  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.  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.  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.  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.  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.  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.   Google Scholar

[12]

F. Hanssmann, "Operations Research in Production and Inventory,", Johnson Wiley & Sons, (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.  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, (2004), 249.   Google Scholar

[15]

M. Khouja, The economic lot and delivery scheduling problem: common cycle, rework, and variable production rate,, IIE Transactions, 32 (2000), 715.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  doi: 10.1287/opre.40.3.551.  Google Scholar

[32]

W. L. Winston, "Operations Research Applications and Algorithms,", PWS-Kent Publishing Company, (1991).   Google Scholar

[33]

C. A. Yano and H. L. Lee, Lot sizing with random yields: A review,, Operations Research, 43 (1995), 311.  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, (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.  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]

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

[3]

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

[4]

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

[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, 2017, 13 (5) : 1-34. doi: 10.3934/jimo.2019030

[6]

Xiaohui Lyu, Nengmin Wang, Zhen Yang, Haoxun Chen. Shipper collaboration in forward and reverse logistics. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-37. doi: 10.3934/jimo.2018173

[7]

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

[8]

Jinling Wei, Jinming Zhang, Meishuang Dong, Fan Zhang, Yunmo Chen, Sha Jin, Zhike Han. Applications of mathematics to maritime search. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 957-968. doi: 10.3934/dcdss.2019064

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

Ganfu Wang, Xingzheng Ai, Chen Zheng, Li Zhong. Strategic inventory with competing suppliers. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2019048

[15]

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

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

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

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

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

[20]

Abdelghani Bouras, Ramdane Hedjar, Lotfi Tadj. Production planning in a three-stock reverse-logistics system with deteriorating items under a periodic review policy. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1075-1089. doi: 10.3934/jimo.2016.12.1075

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (6)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]