Rolling-horizon and fix-and-relax heuristics for the multi-product multi-level capacitated lotsizing problem with sequence-dependent setups

Mohammadi, M.; Fatemi Ghomi, S.; Karimi, B.; Torabi, S.
August 2010
Journal of Intelligent Manufacturing;Aug2010, Vol. 21 Issue 4, p501
Academic Journal
This paper discusses the multi-product multi-level capacitated lotsizing and scheduling problem with sequence-dependent setups. An exact formulation of the problem is provided as a mixed-integer program which is impractical to solve in reasonable computing time for non-small instances. To solve non-small instances of the problem, MIP-based heuristics are provided. To test the accuracy of heuristics, two lower bounds are developed and compared against the optimal solution. The trade-offs between schedule quality and computational time of heuristics are also provided.


Related Articles

  • Hierarchical Production Planning: A Single Stage System. Bitran, Gabriel R.; Haas, Elizabeth A.; Hax, Arnoldo C. // Operations Research;Jul/Aug81, Vol. 29 Issue 4, p717 

    This paper presents a hierarchical approach to plan and schedule production in a manufacturing environment that can be modeled as a single stage process. Initially, the basic tradeoffs inherent to production planning decisions are represented by means of an aggregate model, which is solved on a...

  • INCORPORATING THE STRENGTH OF MIP MODELING IN SCHEDULE CONSTRUCTION. Hurkens, Cor A. J. // RAIRO -- Operations Research;2009, Vol. 43 Issue 4, p409 

    Linear programming techniques can be used in constructing schedules but their application is not trivial. This in particular holds true if a trade-off has to be made between computation time and solution quality. However, it turns out that - when handled with care - mixed integer linear programs...

  • EVALUATION OF A HEURISTIC FOR SCHEDULING INDEPENDENT JOBS ON PARALLEL IDENTICAL PROCESSORS. Dogramaci, Ali; Surkis, Julius // Management Science;Dec1979, Vol. 25 Issue 12, p1208 

    In this paper we consider the problem of scheduling "n" independent tasks on "m" parallel processors. Each job consists of a single operation with a specific processing time and due date. The processors are identical and the operation of the system is non-preemptive. The objective is to schedule...

  • JOB SCHEDULING ALGORITHM BASED ON MULTI-CRITERIA OPTIMIZATION. CZERPAK, PIOTR; ARTIEMJEW, PIOTR // Studia i Materialy Polskiego Stowarzyszenia Zarzadzania Wiedza /;2012, Issue 60, p44 

    The Job Scheduling problem is an important area of research. It is very popular among many researchers from all over the world. However, the Job Scheduling problem is NP-complete; it is impossible to find an algorithm which solves the aforementioned problem in a deterministic way and in...

  • An Improved Genetic Algorithm For Solving The Multiprocessor Scheduling Problem. Al Shaikhli, Imad Fakhri; Khalil, Ismail // Australian Journal of Basic & Applied Sciences;2011, Vol. 5 Issue 12, p947 

    Multiprocessor Scheduling Problem (MSP) is an NP-complete optimization problem. The applications of this problem are numerous, but are, as suggested by the name of the problem, most strongly associated with the scheduling of computational tasks in a multiprocessor environment. Many methods and...

  • Optimization of multi objective Job Shop Scheduling problems using Firefly algorithm. Udaiyakumar, K. C.; Chandrasekaran, M. // Applied Mechanics & Materials;2014, Issue 591, p157 

    Scheduling is the allocation of resources over time to carry out a collection of tasks assigned in any field of engineering and non engineering. Majority of JSSP are categorized into non deterministic (NP) hard problem because of its complexity. Scheduling are generally solved by using...

  • Worst-Case Analysis for a General Class of Online Lot-Sizing Heuristics. Heuvel, Wilco Van den; Wagelmans, Albert P. M. // Operations Research;Jan2010, Vol. 58 Issue 1, p59 

    In this paper, we analyze the worst-case performance of heuristics for the classical economic lot-sizing problem with time-invariant cost parameters. We consider a general class of online heuristics that is often applied in a rolling-horizon environment. We develop a procedure to systematically...

  • Makespan minimization of a flowshop sequence-dependent group scheduling problem. Salmasi, Nasser; Logendran, Rasaratnam; Skandari, Mohammad // International Journal of Advanced Manufacturing Technology;Sep2011, Vol. 56 Issue 5-8, p699 

    The flowshop sequence dependent group scheduling problem with minimization of makespan as the objective ( F|fmls, S, prmu| C) is considered in this paper. It is assumed that several groups with different number of jobs are assigned to a flow shop cell that has m machines. The goal is to find the...

  • A matheuristic approach for the two-machine total completion time flow shop problem. Della Croce, Federico; Grosso, Andrea; Salassa, Fabio // Annals of Operations Research;Feb2014, Vol. 213 Issue 1, p67 

    This paper deals with the two-machine total completion time flow shop problem. We present a so-called matheuristic post processing procedure that improves the objective function value with respect to the solutions provided by state of the art procedures. The proposed procedure is based on the...


Read the Article


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

Try another library?
Sign out of this library

Other Topics