This note is concerned with the bicriteria scheduling problem on a series-batchingmachine to minimize maximum cost and makespan. AnO(n5) algorithm has been establishedpreviously. Here is an improved algorithm which solves the problem inO(n3) time.

A simple idea used in many combinatorial algorithms is the idea ofpivoting. Originally, it comes from the method proposed by Gauss in the19th century for solving systems of linear equations. This method had been extended in1947 by Dantzig for the famous simplex algorithm used for solving linear programs. Fromsince, a pivoting algorithm is a method exploring subsets of a ground set and going fromone subset σ to a new one σ′ by deleting anelement inside σ and adding an element outside σ:σ′ = σ\ { v}  ∪  {u},with v ∈ σ and u ∉ σ.This simple principle combined with other ideas appears to be quite powerful for manyproblems. This present paper is a survey on algorithms in operations research and discretemathematics using pivots. We give also examples where this principle allows not only tocompute but also to prove some theorems in a constructive way. A formalisation isdescribed, mainly based on ideas by Michael J. Todd.

In this paper we present a new approach to solve the Minimum Independent Dominating Setproblem in general graphs which is one of the hardest optimization problem. We propose amethod using a clique partition of the graph, partition that can be obtained greedily. Weprovide conditions under which our method has a better complexity than the complexity ofthe previously known algorithms. Based on our theoretical method, we design in the secondpart of this paper an efficient algorithm by including cuts in the search process. We thenexperiment it and show that it is able to solve almost all instances up to 50 vertices inreasonable time and some instances up to several hundreds of vertices. To go further andto treat larger graphs, we analyze a greedy heuristic. We show that it often gives good(sometimes optimal) results in large instances up to 60   000 vertices in less than 20 s.That sort of heuristic is a good approach to get an initial solution for our exact method.We also describe and analyze some of its worst cases.

This paper broadens the exponential utility function commonly used by risk-averse investors to the linear plus double exponential utility function, which is applicable in most cases. Thus it is of essential and supreme significance to conduct a research on its optimal investment portfolio in securities investment. This paper, by means of the non-difference curve method, carries out a research into the optimal portfolio decision-making by investors who have this type of utility function. The optimal decision-making and the ratio of optimal portfolio investment are derived. Finally, an actual case is given to verify the relevant results.

This paper describes an unreliable server batch arrival retrial queue with two types ofrepair and second optional service. The server provides preliminary first essentialservice (FES) to the primary arriving customers or customers from retrial group. Onsuccessful completion of FES, the customer may opt for second optional service (SOS) withprobability α. The server is subject to active break downs. The customerunder FES (or SOS) during the failure decides, with probability q, tojoin the orbit(impatientcustomer) and, with complementary probabilityp, to remain in the server for repair in order to conclude hisremaining service (patientcustomer). Both service and repair times areassumed to have general distribution. It is considered that the repair time of serverduring the presence of patient customer and the repair time of the server while thecustomer (impatientcustomer) joining the orbit due to failure, aredifferent. For this queueing system, the orbit and system size distributions are obtained.Reliability of the proposed model is analysed. Some particular cases are also discussed.Other performance measures are also obtained. The effects of several parameters on thesystem are analysed numerically.

Tree decomposition introduced by Robertson and Seymour aims to decompose a problem into clusters constituting an acyclic graph. There are works exploiting tree decomposition for complete search methods. In this paper, we show how tree decomposition can be used to efficiently guide local search methods that use large neighborhoods like VNS. We propose DGVNS (Decomposition Guided VNS) which uses the graph of clusters in order to build neighborhood structures enabling better diversification and intensification. Second, we introduce tightness dependent tree decomposition which allows to take advantage of both the structure of the problem and the constraints tightness. Third, experiments performed on random instances (GRAPH) and real life instances (CELAR, SPOT5 and tagSNP) show the appropriateness and the efficiency of our approach. Moreover, we study and discuss the influence of the width of the tree decomposition on our approach and the relevance of removing clusters with very few proper variables from the tree decomposition.

Usual periodic scheduling problems deal with precedence constraints having non-negativelatencies. This seems a natural way for modelling scheduling problems, since task delaysare generally non-negative quantities. However, in some cases, we need to consider edgeslatencies that do not only model task latencies, but model other precedence constraints.For instance in register optimisation problems devoted to optimising compilation, ageneric machine or processor model can allow considering access delays into/fromregisters. Edge latencies may be then non-positive leading to a difficult schedulingproblem in presence of resources constraints. This research result is related to theproblem of periodic scheduling with storage requirement optimisation; its aims is to solvethe practical problem of register optimisation in optimising compilation. We show thatpre-conditioning a data dependence graph (DDG) to satisfy register constraints beforeperiodic scheduling under resources constraints may create circuits with non-positivedistances, resulted from the acceptance of non-positive edge latencies. As a compilerconstruction strategy, it is forbidden to allow the creation of circuits with non-positivedistances during the compilation flow, because such DDG circuits do not guarantee theexistence of a valid instruction schedule under resource constraints. We study twosolutions to avoid the creation of these problematic circuits. A first solution isreactive, it tolerates the creation of non-positive circuit in a first step, and ifdetected in a further check step, makes a backtrack to eliminate them. A second solutionis proactive, it prevents the creation of non-positive circuits in the DDG during theregister optimisation process. It is based on shortest path equations which define anecessary and sufficient condition to free any DDG from these problematic circuits. Thenwe deduce a linear program accordingly. We have implemented our solutions and we presentsuccessful experimental results.

Analysis of empirical sales data lead us to consider newsboy model for four practicalmarket conditions arising from the presence/absence of stochastic lead time and exogenouslinear temporal decline in selling price when distribution of the stochastic demanddepends upon initial selling price. Viability of the solutions is discussed for threestrategies of obtaining optimal initial selling price and/or ordering quantity. Numericalstudies are conducted to assess the effects of lead time and price decline.

Applied research into Renewable Energies raises complex challenges of a technological, economical or political nature. In this paper, we address the techno−economical optimization problem of selecting locations of wind and solar Parks to be built in Egypt, such that the electricity demand is satisfied at minimal costs. Ultimately, our goal is to build a decision support tool that will provide private and governmental investors into renewable energy systems, valuable insights to make informed short and longer term decisions with respect to park creation and placements. Existing approaches have essentially focused on past data to tackle variations of this problem. In this paper, we introduce a novel approach that considers both past and forecast data, and show the impact for accounting for both sets of data and constraints in a two−stage optimization model. We first show that integer linear programming is best suited to solve the past data model compared to Dynamic Programming and Constrained Local Search. We then introduce our two − stage model that accounts for forecast data as well, adding new constraints to the initial model. Our empirical results show that the two − stage model improves solution quality and overall costs, and can be solved effectively to optimality using Integer Linear Programming.

This paper considers the problem of scheduling n jobs on a singlemachine. A fixed processing time and an execution interval are associated with each job.Preemption is not allowed. The objective is to find a feasible job sequence that minimizesthe number of tardy jobs. On the basis of an original mathematical integer programmingformulation, this paper shows how good-quality lower and upper bounds can be computed.Numerical experiments are provided for assessing the proposed approach.

We consider multistage bidding models where two types of risky assets (shares) are tradedbetween two agents that have different information on the liquidation prices of tradedassets. These prices are random integer variables that are determined by the initialchance move according to a probability distribution p over thetwo-dimensional integer lattice that is known to both players. Player 1 is informed on theprices of both types of shares, but Player 2 is not. The bids may take any integer values.The model of n-stage bidding is reduced to a zero-sum repeated game withlack of information on one side. We show that, if liquidation prices of shares have finitevariances, then the sequence of values of n-step games is bounded. This makes itreasonable to consider the bidding of unlimited duration that is reduced to the infinitegame G∞(p). We give the solutions for thesegames. Optimal strategies of Player 1 generate random walks of transaction prices. Butunlike the case of one-type assets, the symmetry of these random walks is broken at thefinal stages of the game.

This work studies a new strategic game called delegation game. A delegation game isassociated to a basic game with a finite number of players where each player has a finiteinteger weight and her strategy consists in dividing it into several integer parts andassigning each part to one subset of finitely many facilities. In the associateddelegation game, a player divides her weight into several integer parts, commits each partto an independent delegate and collects the sum of their payoffs in the basic game playedby these delegates. Delegation equilibrium payoffs, consistent delegation equilibriumpayoffs and consistent chains inducing these ones in a delegation game are defined.Several examples are provided.

In the performance measurement using tools such as data envelopment analysis (DEA), datawithout explicit inputs has attracted considerable attention among researchers. In suchstudies the problem of production planning in the next production season is an importantand interesting subject. Because of the uncertain nature of the future, decision makersneed to provide robust procedures in order to examine alternative courses of action andtheir implications. The purpose of this paper is to develop an approach to productionplanning problem in production processes without explicit inputs that typically appears incentralized decision making environment. Application of the proposed approach isillustrated empirically using a real case.

Application tools for the crop allocation problem (CAP) are required for agricultural advisors to design more efficient farming systems. Despite the extensive treatment of this issue by agronomists in the past, few methods tackle the crop allocation problem considering both the spatial and the temporal aspects of the CAP. In this paper, we precisely propose an original formulation addressing the crop allocation planning problem while taking farmers’ management choices into account. These choices are naturally represented by hard and soft constraints in the Weighted CSP formalism. We illustrate our proposition by solving a medium–size virtual farm using either a WCSP solver (toulbar2) or an ILP solver (NumberJack/SCIP). This preliminary work foreshadows the development of a decision–aid tool for supporting farmers in their crop allocation strategies.

The rising car usage deriving from growth in jobs and residential population causes airpollution, energy waste and consumption of people’s time. Public transport cannot be theonly answer to this increasing transport demand. Carpooling, which is based on the ideathat sets of car owners pick up colleagues while driving to or from the workplace, hasemerged to be a viable possibility for reducing private car usage in congested areas. Itsactual practice requires a suitable information system support and, the most important,the capability of effectively solving the underlying combinatorial optimization problem.This paper describes an ant colony algorithm based hybrid approach (HAC) for solving themulti-destination carpooling problem. Experiments have been performed to confirm theefficiency and the effectiveness of the approach.

Simple Temporal Networks (STN) allow conjunctions of minimum and maximum distance constraints between pairs of temporal positions to be represented. This paper introduces an extension of STN called Time–dependent STN (TSTN), which covers temporal constraints for which the minimum and maximum distances required between two temporal positions x and y are not necessarily constant but may depend on the assignments of x and y. Such constraints are useful to model problems in which the duration of an activity may depend on its starting time, or problems in which the transition time required between two activities may depend on the time at which the transition is triggered. Properties of the new framework are analyzed, and standard STN solving techniques are extended to TSTN. The contributions are applied to the management of temporal constraints for so-called agile Earth observation satellites.

In this paper, we show that the direct semidefinite programming (SDP) bound for thenonconvex quadratic optimization problem over ℓ1 unit ball(QPL1) is equivalent to the optimal d.c. (difference between convex) bound for thestandard quadratic programming reformulation of QPL1. Then we disprove a conjecture aboutthe tightness of the direct SDP bound. Finally, as an extension of QPL1, we study therelaxation problem of the sparse principal component analysis, denoted by QPL2L1. We showthat the existing direct SDP bound for QPL2L1 is equivalent to the doubly nonnegativerelaxation for variable-splitting reformulation of QPL2L1.

For solving linear complementarity problems LCP more attention has recently been paid on a class of iterative methods called the matrix-splitting. But up to now, no paper has discussed the effect of preconditioning technique for matrix-splitting methods in LCP. So, this paper is planning to fill in this gap and we use a class of preconditioners with generalized Accelerated Overrelaxation (GAOR) methods and analyze the convergence of these methods for LCP. Furthermore, Comparison between our methods and other non-preconditioned methods for the studied problem shows a remarkable agreement and reveals that our models are superior in point of view of convergence rate and computing efficiency. Besides, by choosing the appropriate parameters of these methods, we derive same results as the other iterative methods such as AOR, JOR, SOR etc. Finally the method is tested by some numerical experiments.