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 andcapacity constraints. The problem is reformulated according to a multi-commodity flowformalism, and decomposed, through Lagrangean relaxation, into a master facility locationproblem and a slave minimal cost multi-commodity flow problem. The decomposition frameworkgives rise in a natural way to designing a Lagrangean based heuristic. Numericalexperiments showing the efficiency of the proposed approach are reported.

In matricial analysis, the theorem of Eckart and Young provides a best approximation ofan arbitrary matrix by a matrix of rank at most r. In variationalanalysis or optimization, the Moreau envelopes are appropriate ways of approximating orregularizing the rank function. We prove here that we can go forwards and backwardsbetween the two procedures, thereby showing that they carry essentially the sameinformation.

One-fund theorem states that an efficient portfolio in a Mean-Variance (M-V) portfolioselection problem for a set of some risky assets and a riskless asset can be representedby a combination of a unique risky fund (tangency portfolio) and the riskless asset. Inthis paper, we introduce a method for which the tangency portfolio can be produced as acorner portfolio. So, the tangency portfolio can be computed easily and fast by anyalgorithm designed for tracing out the M-V efficient frontier via computing the cornerportfolios. Moreover, we show that how this method can be used for tracing out the M-Vefficient frontier when problem contains a riskless asset in which the borrowing is notallowed.

This paper aims at developing efficient solving methods for an original service networkdesign problem imbued with sustainable issues. Indeed the network has to be designed forshort and local supply chain and for fresh food products. The original features of theproblem are the seasonality of supply, the limitation of transshipments for a product andno possibility of storage between consecutive periods. Decisions at strategic and tacticallevel are (1) decisions on a subset of hubs to open among a given set of potentiallocations, (2) transportation services to open between the actors and (3) flow quantitiesfor the fresh food products. We propose for this problem a Mixed Integer Programmingformulation and two solving techniques: Benders Decomposition and Dynamic Slope ScalingProcedure. These techniques are adapted to the problem and some experimental tests areconducted in order to compare the approaches on large-scale instances.

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

In this paper we present a robust real-time optimization method for the online linear oilblending process. The blending process consists in determining the optimal mix ofcomponents so that the final product satisfies a set of specifications. We examinedifferent sources of uncertainty inherent to the blending process and show how to addressthis uncertainty applying the Robust Optimization techniques. The polytopal structure ofour problem permits a simplified robust approach. Our method is intended to avoidreblending and we measure its performance in terms of the blend quality giveaway andfeedstocks prices. The difference between the nominal and the robust optimal values (theprice of robustness) provides a benchmark for the cost of reblending which is difficult toestimate in practice. This new information can be used to adjust the level of conservatismin the model. We analyze the feasibility of a blend to be produced from a set offeedstocks 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 searchand a constructive optimization algorithm for a large-scale energy management andmaintenance scheduling problem. The methodology shows how to successfully combine andorchestrate different types of algorithms and to produce competitive results. We alsopropose an efficient way to scale the method for huge instances. A large part of thepresented work was done to compete in the ROADEF/EURO Challenge 2010, organized jointly bythe ROADEF, EURO and Électricité de France. The numerical results obtained on officialcompetition instances testify about the quality of the approach. The method achieves 3 outof 15 possible best results.