An MIP-based interval heuristic for the capacitated multi-level lot-sizing problem with setup times

Wu, Tao; Shi, Leyuan; Song, Jie
June 2012
Annals of Operations Research;Jun2012, Vol. 196 Issue 1, p635
Academic Journal
This paper considers the capacitated multi-level lot-sizing problem with setup times, a class of difficult problems often faced in practical production planning settings. In the literature, relax-and-fix is a technique commonly applied to solve this problem due to the fact that setup decisions in later periods of the planning horizon are sensitive to setup decisions in the early periods but not vice versa. However, the weakness of this method is that setup decisions are optimized only on a small subset of periods in each iteration, and setup decisions fixed in early iterations might adversely affect setup decisions in later periods. In order to avoid these weaknesses, this paper proposes an extended relax-and-fix based heuristic that systematically uses domain knowledge derived from several strategies of relax-and-fix and a linear programming relaxation technique. Computational results show that the proposed heuristic is superior to other well-known approaches on solution qualities, in particular on hard test instances.


Related Articles

  • Solving the electricity production planning problem by a column generation based heuristic. Rozenknop, Antoine; Wolfler Calvo, Roberto; Alfandari, Laurent; Chemla, Daniel; Létocart, Lucas // Journal of Scheduling;Dec2013, Vol. 16 Issue 6, p585 

    This paper presents a heuristic method based on column generation for the EDF (Electricité De France) long-term electricity production planning problem proposed as subject of the ROADEF/EURO 2010 Challenge. This is to our knowledge the first-ranked method among those methods based on...

  • A Heuristic Approach to Solve Production Planning Problem with Machine Failure in a Series Parallel Multi-State System. Gajpal, Yuvraj; Nourelfath, Mustapha // Proceedings of the International Conference on Industrial Engine;2014, p1299 

    We consider a production system containing a set of machines which are arranged according to a series-parallel configuration. The machines are unreliable and the failure rate of machine depends on the load assigned to the machine. The expected performance of the system is considered to be a...

  • A Relax-and-Fix Heuristic for a Production Planning Problem with Order Acceptance and Flexible Due Dates. Brahimi, N. // Proceedings of the International Conference on Industrial Engine;2014, p2303 

    We present a new production planning problem which integrates order acceptance decisions with due date flexibility while taking into consideration realistic production capacity constraints. The problem consists of choosing among a set of customer orders which ones to accept based on the profit...

  • The basic train makeup problem in shunting yards. Boysen, Nils; Emde, Simon; Fliedner, Malte // OR Spectrum;Jan2016, Vol. 38 Issue 1, p207 

    In shunting yards, railcars of incoming trains are uncoupled and reassembled to outbound trains. This time-critical process that employs a complex system of switches, hump hills, and classification tracks requires plenty interdependent decision problems to be solved. An elementary decision task...

  • EFD: a model building approach—3. Southworth, Alan // Accountancy;Oct76, Vol. 87 Issue 998, p101 

    This article examines the techniques available to help management in making investment appraisal decisions under conditions of capital rationing. It is found that the main advantage of a linear program was that it considered the combined effect of all the constraints upon the decision variables,...

  • A NOTE ON "MARKOVIAN DECISION MODELS FOR REJECT ALLOWANCE PROBLEMS" Awate, Prakash G. // Management Science;Jan1972 Part 1, Vol. 18 Issue 5, p339 

    This note makes two contributions to M. Klein's formulation of the multiperiod reject allowance problem. First, a decomposition algorithm involving both linear and dynamic programming is proposed, and its computational savings over the straight simplex method are demonstrated. Second, in Klein's...

  • Simultaneous berth allocation and yard planning at tactical level. Hendriks, M.; Lefeber, E.; Udding, J. // OR Spectrum;Mar2013, Vol. 35 Issue 2, p441 

    We present a simultaneous berth allocation and yard planning problem at tactical level, since the berth allocation has a great impact on the yard planning and vice versa. This problem is solved by means of an alternating berth and yard planning heuristic approach. The alternating heuristic...

  • Two-stage flow-shop scheduling problem with non-identical second stage assembly machines. Navaei, J.; Ghomi, S. M. T. Fatemi; Jolai, F.; Shiraqai, M. E.; Hidaji, H. // International Journal of Advanced Manufacturing Technology;Dec2013, Vol. 69 Issue 9-12, p2215 

    This paper addresses the two-stage assembly flow-shop problem (TSAFP) with multiple non-identical assembly machines in second stage with the objective function of makespan minimization. This problem is a generalization of previously proposed problems in TSAFP. Mathematical mixed-integer linear...

  • Semidefinite Programming Based Algorithms for the Sparsest Cut Problem. Meira, Luis A.A.; Miyazawa, Flávio K. // RAIRO -- Operations Research;Apr2011, Vol. 45 Issue 2, p75 

    In this paper we analyze a known relaxation for the Sparsest Cut problem based on positive semidefinite constraints, and we present a branch and bound algorithm and heuristics based on this relaxation. The relaxed formulation and the algorithms were tested on small and moderate sized instances....


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics