We give a new formulation for the problem of task scheduling intounrelated processors under precedence constraints. This formulation has a polynomial number of variables and does not require that theprocessing times be integer valued.

In this work scheduling multiprocessor tasks on two parallel identical processors is considered.Multiprocessor tasks can be executed by more than one processorat the same moment of time.We analyze scheduling unit execution time and preemptable tasks to minimize schedule length and maximum lateness.Cases with ready times, due-dates and precedence constraintsare discussed.

The two-dimensional bin packing problem is a well-known problem for which several exact and approximation methods were proposed. In real life applications, such as in Hazardous Material transportation, transported items may be partially incompatible, and have to be separated by a safety distance. This complication has not yet been considered in the literature. This paper introduces this extension called the two-dimensional bin packing problem with partial conflicts (2BPPC) which is a 2BP with distance constraints between given items to respect, if they are packed within a same bin. The problem is NP-hard since it generalizes the BP, already NP-hard. This study presents a mathematical model, two heuristics and a multi-start genetic algorithm for this new problem.

This paper investigates an inventory control problem where a firm orders and sells an inventory item through discount strategy in a price sensitive market. From the economic points of view, customers may expect a further price reduction when a firm uses pricing promotion to stimulate demand, the demand curve may vertically shift down when a firm reduces the selling price. Taking these phenomena into account, this paper developed a continuous inventory model for finding the ordering quantity, the number of pricing changing and times of price changes simultaneously so as to maximize the total profit. A solution procedure is developed for finding the optimal decision rules.

Recently, Y.Q. Bai, M. El Ghami and C. Roos [3] introduced a new class ofso-called eligible kernel functions which are defined by somesimple conditions.The authors designed primal-dual interior-point methods for linear optimization (LO)based on eligible kernel functionsand simplified the analysis of these methods considerably.In this paper we consider the semidefinite optimization (SDO) problemand we generalize the aforementioned results for LO to SDO.The iteration bounds obtained are analogous to the results in [3] for LO.

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.

In this paper, we propose a nonlinear multi-objective optimization problem whoseparameters in the objective functions and constraints vary in between some lower and upperbounds. Existence of the efficient solution of this model is studied and gradient based aswell as gradient free optimality conditions are derived. The theoretical developments areillustrated through numerical examples.

For a specific query merging the returned results from multiple search engines, in theform of a metasearch aggregation, can provide significant improvement in the quality ofrelevant documents. This paper suggests a minimax linear programming (LP) formulation forfusion of multiple search engines results. The paper proposes a weighting method toinclude the importance weights of the underlying search engines. This is a two-phaseapproach which in the first phase a new method for computing the importance weights of thesearch engines is introduced and in the second stage a minimax LP model for findingrelevant search engines results is formulated. To evaluate the retrieval effectiveness ofthe suggested method, the 50 queries of the 2002 TREC Web track were utilized andsubmitted to three popular Web search engines called Ask, Bing and Google. The returnedresults were aggregated using two exiting approaches, three high-performance commercialWeb metasearch engines and our proposed technique. The efficiency of the generated listswas measured using TREC-Style Average Precision (TSAP). The new findings demonstrate thatthe suggested model improved the quality of merging considerably.

In this paper, information theoretic methodology forsystem modeling is applied to investigate the probability density functionof the busy period in M/G/1 vacation models operating under the N-, T- andD-policies. The information about the density function is limited to a fewmean value constraints (usually the first moments). By using the maximumentropy methodology one obtains the least biased probability densityfunction satisfying the system's constraints. The analysis of the threecontrollable M/G/1 queueing models provides a parallel numerical study ofthe solution obtained via the maximum entropy approach versus “classical”solutions. The maximum entropy analysis of a continuous system descriptor(like the busy period) enriches the current body of literature which, inmost cases, reduces to discrete queueing measures (such as the number ofcustomers in the system).

We consider a firmthat sells seasonal goods. The firm seeks to reach a fixed levelof goodwill at the end of the selling period, with the minimumtotal expenditure in promotional activities. We consider thelinear optimal control problem faced by the firm which can onlycontrol the communication expenditure rate; communication isperformed by means of advertising and sales promotion. Goodwilland sales levels are considered as state variables andword-of-mouth effect and saturation aversion are taken intoaccount. The optimal control problem is addressed by means of theclassical Pontryagin Maximum Principle and the solution can beeasily found solving, in some cases numerically, a system of twonon linear equations. Moreover, a parametric analysis is performedto understand how the total expenditure in communication shouldbe divided between advertising and sales promotion.

This paper presents a feasible primal algorithm for linear semidefinite programming. The algorithm starts with a strictly feasible solution, but in case where no such a solution is known, an application of the algorithm to an associate problem allows to obtain one. Finally, we present some numerical experiments which show that the algorithm works properly.

We study a deterministic problem of evaluating the worst case performance of flexible solutions in the single machine scheduling. A flexible solution is a set of schedules following a given structure determined by a partial order of jobs and a type of the schedules. In this paper, the schedules of active and non-delay type are considered. A flexible solution can be used on-line to absorb the impact of data disturbances related to, for example, job arrival, tool availability or machine breakdowns. The performance of a flexible solution includes the best case and the worst case performances. The best case performance is an ideal performance that can be achieved only if the on-line conditions allow to implement the best schedule of the set of schedules characterizing the flexible solution. In contrast, the worst case performance indicates how poorly the flexible solution may perform when following the given structure in the on-line circumstances. The best-case and the worst-case performances are usually evaluated by the minimum and maximum values of the considered objective function, respectively. We present algorithmic and computational complexity results for some maximization scheduling problems. In these problems, the jobs to be scheduled have different release dates and precedence constraints may be given on the set of jobs.

An algorithm for enumerating all nondominated vectors of multiple objectiveinteger linear programs is presented. The method tests different regionswhere candidates can be found using an auxiliary binary problem for trackingthe regions already explored. An experimental comparision with our previousefforts shows the method has relatively good time performance.

In the paper, the problem of the genome mapping of DNA molecules, is presented. In particular, the new approach — the Simplified Partial Digest Problem (SPDP), is analyzed. This approach, although easy in laboratory implementation and robust with respect to measurement errors, when formulated in terms of a combinatorial search problem, is proved to be strongly NP-hard for the general error-free case. For a subproblem of the SPDP, a simple O(nlogn)-time algorithm is given, where n is a number of restriction sites.

In this paper, we propose a new method to generate a continuousbelief functions from a multimodal probability distribution function definedover a continuous domain. We generalize Smets' approach in the sense thatfocal elements of the resulting continuous belief function can be disjoint setsof the extended real space of dimension n. We then derive the continuousbelief function from multimodal probability density functions using the leastcommitment principle. We illustrate the approach on two examples of probabilitydensity functions (unimodal and multimodal). On a case study of Search AndRescue (SAR), we extend the traditional probabilistic framework of search theoryto continuous belief functions theory. We propose a new optimization criterionto allocate the search effort as well as a new rule to update the informationabout the lost object location in this latter framework. We finally compare theallocation of the search effort using this alternative uncertaintyrepresentation to the traditional probabilistic representation.

A single-server queueing system with a batch Markovian arrivalprocess (BMAP) and MAP-input of disasters causing all customers toleave the system instantaneously is considered. The system has twooperation modes, which depend on the current queue length. Theembedded and arbitrary time stationary queue length distributionhas been derived and the optimal control threshold strategy hasbeen determined.

Many well-known combinatorial optimization problems can be stated over the set of acyclic orientationsof an undirected graph. For example, acyclic orientations with certain diameter constraints areclosely related to the optimal solutions of the vertex coloring and frequency assignment problems. In this paper we introduce a linear programming formulation of acyclic orientationswith path constraints, and discuss its use in the solution of the vertex coloring problem andsome versions of the frequency assignment problem. A study of the polytope associated with the formulation is presented, including proofs of which constraints of the formulation are facet-definingand the introduction of new classes of valid inequalities.

This paper aims at proposing tractable algorithms to find effectively good solutions to large size chance-constrained combinatorial problems. A new robust model is introduced to deal with uncertainty in mixed-integer linear problems. It is shown to be strongly related to chance-constrained programming when considering pure 0–1 problems. Furthermore, its tractability is highlighted. Then, an optimization algorithm is designed to provide possibly good solutions to chance-constrained combinatorial problems. This approach is numerically tested on knapsack and multi-dimensional knapsack problems. The results obtained outperform many methods based on earlier literature.

We consider the NP Hard problems of online Bin Covering and Packing whilerequiring that larger (or longer, in the one dimensional case)items be placed at the bottom of the bins, below smaller (orshorter) items — we call such a version, the LIBversion of problems. Bin sizes can be uniform or variable. We lookat computational studies for both the Best Fit and Harmonic Fitalgorithms for uniform sized bin covering. The Best Fit heuristic forthis version of the problem is introduced here. The approximation ratios obtained were well within the theoretical upperbounds. For variable sized bin covering, a more thorough analysis revealeddefinite trends in the maximum and average approximation ratios. Finally, we prove that for online LIB bin packing with uniform sizebins, no heuristic can guarantee an approximation ratio better than1.76 under the online model considered.

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.