Formulating and solving a multi-mode resource-collaboration and constrained scheduling problem (MRCCSP)

Pinto, Gaby; Ben-Dov, Yariv; Rabinowitz, Gad
July 2013
Annals of Operations Research;Jul2013, Vol. 206 Issue 1, p311
Academic Journal
The main motivation of this study is to provide, for the first time, a formulation and solution for a class of production scheduling problems (as in cluster tools) characterized mainly by resource collaboration to perform an operation and while allowing batches and considering alternative production methods. We develop a formulation for the new problem and term it a multiple mode per operation, resource collaboration, and constrained scheduling problem (MRCCSP). Some of the important new characteristics we consider are: multiple products (families); multiple orders (jobs) per family; precedence restrictions among the operations that constitute a job; alternative modes for the performance of an operation (each of which needs a set of collaborating resources) may be defined; complementary and exclusive restrictions between operation-modes; batch production is allowed; and setup times may depend on sequence and batch-size. The objective of the MRCCSP is to minimize makespan. We formulate the MRCCSP as a mixed integer linear programming model, and acknowledging the considerable size of the monolithic formulation required, we prescribe a specific method to achieve size reduction. Finally, a customized branch and bound algorithm for optimally solving this problem is proposed and examined experimentally.


Related Articles

  • MineLib: a library of open pit mining problems. Espinoza, Daniel; Goycoolea, Marcos; Moreno, Eduardo; Newman, Alexandra // Annals of Operations Research;Jul2013, Vol. 206 Issue 1, p93 

    Similar to the mixed-integer programming library (MIPLIB), we present a library of publicly available test problem instances for three classical types of open pit mining problems: the ultimate pit limit problem and two variants of open pit production scheduling problems. The ultimate pit limit...

  • A 0–1 integer linear programming approach to schedule outages of nuclear power plants. Jost, V.; Savourey, D. // Journal of Scheduling;Dec2013, Vol. 16 Issue 6, p551 

    We address the problem of planning outages of nuclear power plants submitted by EDF (Électricité De France) as the challenge EURO/ROADEF 2010. As our team won the first prize of the contest in the senior category, our approach may be of interest: it is conceptually simple, easy to program...

  • Robust Optimization of Schedules Affected by Uncertain Events. Vujanic, Robin; Goulart, Paul; Morari, Manfred // Journal of Optimization Theory & Applications;Dec2016, Vol. 171 Issue 3, p1033 

    In this paper, we present a new method for finding robust solutions to mixed-integer linear programs subject to uncertain events. We present a new modeling framework for such events that result in uncertainty sets that depend parametrically on the decision taken. We also develop results that can...

  • Covering Linear Programming with Violations. Feng Qiu; Ahmed, Shabbir; Dey, Santanu S.; Wolsey, Laurence A. // INFORMS Journal on Computing;Summer2014, Vol. 26 Issue 3, p531 

    We consider a class of linear programs involving a set of covering constraints of which at most k are allowed to be violated. We show that this covering linear program with violation is strongly NP-hard. To improve the performance of mixed-integer programming-based schemes for these problems, we...

  • Mixed integer programming models for two identical parallel machines with a single server. Yong Zhan; Haitao Zhu; Yuguang Zhong // Advanced Materials Research;2014, Vol. 945-949, p3344 

    This paper addresses the problem of scheduling jobs on two identical parallel machines with a single server such that the makespan is minimized. Each job can be processed by either one of the two parallel machines, but before processing, a setup operation must be done by a single server. Two...

  • A genetic algorithm for the simultaneous lot sizing and scheduling problem in capacitated flow shop with complex setups and backlogging. Babaei, M.; Mohammadi, M.; Ghomi, S. // International Journal of Advanced Manufacturing Technology;Jan2014, Vol. 70 Issue 1-4, p125 

    In this paper the capacitated lot sizing and scheduling problem with sequence-dependent setups, setup carryover, and backlogging has been studied. The problem can be formulated as a mixed-integer program. Most lot sizing problems are hard to solve, especially in medium and large scale. In recent...

  • Improved estimation of distribution algorithm for the problem of single-machine scheduling with deteriorating jobs and different due dates. Wu, Hua-Ping; Huang, Min // Computational & Applied Mathematics;Oct2014, Vol. 33 Issue 3, p557 

    This paper investigates single-machine scheduling problem, which is an NP-hard problem, with deteriorating jobs and different due dates to minimize total tardiness. First, two special polynomially solvable cases of the problem and a mixed-integer programming (MIP) model are proposed. Since the...

  • Application of an effective modified gravitational search algorithm for the coordinated scheduling problem in a two-stage supply chain. Pei, Jun; Liu, Xinbao; Pardalos, Panos; Fan, Wenjuan; Yang, Shanlin; Wang, Ling // International Journal of Advanced Manufacturing Technology;Jan2014, Vol. 70 Issue 1-4, p335 

    This paper investigates a products and vehicles scheduling problem in a two-stage supply chain environment, where jobs first need to be processed on the serial batching machines of multiple manufacturers distributed in various geographic zones and then transported by vehicles to a customer for...

  • Combining Lift-and-Project and Reduce-and-Split. Balas, Egon; Cornuéjols, Gérard; Kis, Tamás; Nannicini, Giacomo // INFORMS Journal on Computing;Summer2013, Vol. 25 Issue 3, p475 

    Split cuts constitute a class of cutting planes that has been successfully employed by the majority of branch-and-cut solvers for mixed-integer linear programs. Given a basis of the linear programming (LP) relaxation and a split disjunction, the corresponding split cut can be computed with a...


Read the Article


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

Try another library?
Sign out of this library

Other Topics