We consider the scheduling of an interval order precedence graph of unit execution time tasks with communication delays, release dates and deadlines. Tasks must be executed by a set of processors partitioned into K classes; each task requires one processor from a fixed class. The aim of this paper is to study the extension of the Leung–Palem–Pnueli (in short LPP) algorithm to this problem. The main result is to prove that the LPP algorithm can be extended to dedicated processors and monotone communication delays. It is also proved that the problem is NP–complete for two dedicated processors if communication delays are non monotone. Lastly, we show that list scheduling algorithm cannot provide a solution for identical processors.

The paper addresses a multi-item, multi-plant lot-sizing problem with transfer costs and capacity constraints. The problem is reformulated according to a multi-commodity flow formalism, and decomposed, through Lagrangean relaxation, into a master facility location problem and a slave minimal cost multi-commodity flow problem. The decomposition framework gives rise in a natural way to designing a Lagrangean based heuristic. Numerical experiments showing the efficiency of the proposed approach are reported.

In matricial analysis, the theorem of Eckart and Young provides a best approximation of an arbitrary matrix by a matrix of rank at most r. In variational analysis or optimization, the Moreau envelopes are appropriate ways of approximating or regularizing the rank function. We prove here that we can go forwards and backwards between the two procedures, thereby showing that they carry essentially the same information.

One-fund theorem states that an efficient portfolio in a Mean-Variance (M-V) portfolio selection problem for a set of some risky assets and a riskless asset can be represented by a combination of a unique risky fund (tangency portfolio) and the riskless asset. In this paper, we introduce a method for which the tangency portfolio can be produced as a corner portfolio. So, the tangency portfolio can be computed easily and fast by any algorithm designed for tracing out the M-V efficient frontier via computing the corner portfolios. Moreover, we show that how this method can be used for tracing out the M-V efficient frontier when problem contains a riskless asset in which the borrowing is not allowed.

This paper aims at developing efficient solving methods for an original service network design problem imbued with sustainable issues. Indeed the network has to be designed for short and local supply chain and for fresh food products. The original features of the problem are the seasonality of supply, the limitation of transshipments for a product and no possibility of storage between consecutive periods. Decisions at strategic and tactical level are (1) decisions on a subset of hubs to open among a given set of potential locations, (2) transportation services to open between the actors and (3) flow quantities for the fresh food products. We propose for this problem a Mixed Integer Programming formulation and two solving techniques: Benders Decomposition and Dynamic Slope Scaling Procedure. These techniques are adapted to the problem and some experimental tests are conducted in order to compare the approaches on large-scale instances.

To model the dynamics of discrete deterministic systems, we extend the Petri nets framework by a priority relation between conflicting transitions, which is encoded by orienting the edges of a transition conflict graph. The aim of this paper is to gain some insight into the structure of this conflict graph and to characterize a class of suitable orientations by an analysis in the context of hypergraph theory.

In this paper we present a robust real-time optimization method for the online linear oil blending process. The blending process consists in determining the optimal mix of components so that the final product satisfies a set of specifications. We examine different sources of uncertainty inherent to the blending process and show how to address this uncertainty applying the Robust Optimization techniques. The polytopal structure of our problem permits a simplified robust approach. Our method is intended to avoid reblending and we measure its performance in terms of the blend quality giveaway and feedstocks prices. The difference between the nominal and the robust optimal values (the price of robustness) provides a benchmark for the cost of reblending which is difficult to estimate in practice. This new information can be used to adjust the level of conservatism in the model. We analyze the feasibility of a blend to be produced from a set of feedstocks when the heel of a previous blend is used in the composition of the new blend. Additional critical information for the control system is then produced.

This paper presents a heuristic approach combining constraint satisfaction, local search and a constructive optimization algorithm for a large-scale energy management and maintenance scheduling problem. The methodology shows how to successfully combine and orchestrate different types of algorithms and to produce competitive results. We also propose an efficient way to scale the method for huge instances. A large part of the presented work was done to compete in the ROADEF/EURO Challenge 2010, organized jointly by the ROADEF, EURO and Électricité de France. The numerical results obtained on official competition instances testify about the quality of the approach. The method achieves 3 out of 15 possible best results.