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

Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021037

[2]

Gaurav Nagpal, Udayan Chanda, Nitant Upasani. Inventory replenishment policies for two successive generations price-sensitive technology products. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021036

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]