In a multi server queuing system, buffer size is often larger than the number of servers.This necessitates queuing and waiting for some customers. Customers become impatient whilewaiting for service. Additionally, they may also become impatient if service is notoffered at the desired rate. This paper analyses a finite buffer multi server queuingsystem with the additional restriction that customers may balk as well as renege. Closedform expressions of a number of performance measures are presented. A design problem isdiscussed to demonstrate the results derived.

In this paper, we study the problem of makespan minimization for the multiprocessorscheduling problem in the presence of communication delays. The communication delaybetween two tasks i and j depends on the distancebetween the two processors on which these two tasks are executed. Lahlou shows that asimple polynomial-time algorithm exists when the length of the schedule is at most two(the problem becomes 𝒩𝒫-complete when the length of the scheduleis at most three). We prove that there is no polynomial-time algorithm with a performanceguarantee of less than 4/3 (unless 𝒫 = 𝒩𝒫) to minimizethe makespan when the network topology is a chain or ring and the precedence graph is abipartite graph of depth one. We also develop two polynomial-time approximation algorithmswith constant ratio dedicated to cases where the processor network admits a limited orunlimited number of processors.

One of the important issues on the distribution network design is to incorporateinventory management cost into the facility location model. This paper deals with anetwork model making the decisions on the facility location such as the number of DCs andtheir locations as well as the decisions on the inventory management such as the orderingquantity and the level of safety stock at each DC. The considered model differs from theprevious works by classifying the related costs into the operating cost and the investmentcost. For this model, a solution procedure based on the Lagrangian relaxation method wasproposed and tested for its effectiveness with various 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, a batch arrival general bulk service queueing system with interruptedvacation (secondary job) is considered. At a service completion epoch, if the server findsat least ‘a’ customers waiting for service say ξ, heserves a batch of min (ξ, b) customers, whereb ≥ a. On the other hand, if the queue length is atthe most ‘a-1’, the server leaves for a secondary job (vacation) ofrandom length. It is assumed that the secondary job is interrupted abruptly and the serverresumes for primary service, if the queue size reaches ‘a’, during thesecondary job period. On completion of the secondary job, the server remains in the system(dormant period) until the queue length reaches ‘a’. For the proposedmodel, the probability generating function of the steady state queue size distribution atan arbitrary time is obtained. Various performance measures are derived. A cost model forthe queueing system is also developed. To optimize the cost, a numerical illustration isprovided.

This paper deals with the parallel-machine scheduling problem with the aim of minimizingthe total (weighted) tardiness under the assumption of different release dates. Thisproblem has been proven to be NP-hard. We introduce some new lower and upper bounds basedon different approaches. We propose a branch-and-bound algorithm to solve the weighted andunweighted total tardiness. Computational experiments were performed on a large set ofinstances and the obtained results showed that our algorithms are efficient.

The minimum cost network flow problem, (MCNFP) constitutes a wide category of networkflow problems. Recently a new dual network exterior point simplex algorithm (DNEPSA) forthe MCNFP has been developed. This algorithm belongs to a special “exterior point simplextype” category. Similar to the classical dual network simplex algorithm (DNSA), thisalgorithm starts with a dual feasible tree-solution and after a number of iterations, itproduces a solution that is both primal and dual feasible, i.e. it isoptimal. However, contrary to the DNSA, the new algorithm does not always maintain a dualfeasible solution. Instead, it produces tree-solutions that can be infeasible for the dualproblem and at the same time infeasible for the primal problem. In this paper, we presentfor the first time, the mathematical proof of correctness of DNEPSA, a detailedcomparative computational study of DNEPSA and DNSA on sparse and dense random probleminstances, a statistical analysis of the experimental results, and finally some newresults on the empirical complexity of DNEPSA. The analysis proves the superiority ofDNEPSA compared to DNSA in terms of cpu time and iterations.

This paper presents a hybrid schedule generation scheme for solving theresource-constrained project scheduling problem. The scheme, which is called the PolarizedAdaptive Scheduling Scheme (PASS), can operate in a spectrum between two poles, namely theparallel and serial schedule generation schemes. A polarizer parameter in the rangebetween zero and one indicates how similarly the PASS behaves like each of its two poles.The presented hybrid is incorporated into a novel genetic algorithm that neverdegenerates, resulting in an effective self-adaptive procedure. The key point of thisgenetic algorithm is the embedding of the polarizer parameter as a gene in the genomesused. Through this embedding, the procedure learns via monitoring its ownperformance and incorporates this knowledge in conducting the search process. Thecomputational experiments indicate that the procedure can produce optimal solutions for alarge percentage of benchmark instances.

The paper focuses on multi-criteria problems. It presents the interactive compromise hypersphere method with sensitivity analysis as a decision tool in multi-objective programming problems. The method is based on finding a hypersphere (in the criteria space) which is closest to the set of chosen nondominated solutions. The proposed modifications of the compromise hypersphere method are based on using various metrics and analyzing their influence on the original method. Applications of the proposed method are presented in four multi-criteria problems: the assignment problem, the knapsack problem, the project management problem and the manufacturing problem.

The coupled tasks scheduling problem is a class of scheduling problems introduced forbeam steering software of sophisticated radar devices, called phased arrays. Due toincreasing popularity of such radars, the importance of coupled tasks scheduling isconstantly growing. Unfortunately, most of the coupled tasks problems are NP-hard, andonly a few practically usable algorithms for such problems were found. This paper providesa survey of already known complexity results of various variants of coupled tasksproblems. Then, it complements previous results by providing experimental results of twonew polynomial algorithms for coupled tasks scheduling, which are: an exact algorithm for1|(1,4,1),strictchains|Cmax problem,and a fast heuristic algorithm for more general1|(1,2k, 1), strictchains|Cmaxproblem, where k ∈ ℕ.

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.

A risk measure in a portfolio selection problem is linear programming (LP) solvable, ifit has a linear formulation when the asset returns are represented by discrete randomvariables, i.e., they are defined by their realizations under specifiedscenarios. The efficient frontier corresponding to an LP solvable model is a piecewiselinear curve. In this paper we describe a method which realizes and produces a tangencyportfolio as a by-product during the procedure of tracing out of the efficient frontier ofrisky assets in an LP solvable model, when our portfolio contains some risky assets and ariskless asset, using nonsmooth optimization methods. We show that the test of finding thetangency portfolio can be limited only for two portfolios. Also, we describe that how thismethod can be employed to trace out the efficient frontier corresponding to a portfolioselection problem in the presence of a riskless asset.

The risk of demand or production cost disruption is one of the challenging problems in the supply chain management. This paper explores a generalized supply chain game model incorporating the possible disruptions. We find that a nonlinear Grove wholesale price scheme can fully coordinate such a supply chain even when both market demand and production cost are disrupted. The nonlinear Grove wholesale price scheme has three sides to coordinate the decision behavior of the players. One is that the mechanism can induce the retail pricing decided by the dominant retailer to be equal with that of the channel; the second is that the mechanism can induce fringe retailers to be not priced out of the market; the third is that the mechanism can ensure that the manufacturer uses minimum incentives to induce the dominant retailer to sell its product as well as providing the demand-stimulating service. Disruptions from both demand side and production cost side may also affect the wholesale price, order quantity as well as retail price, and the share of the dominant retailer and the subsidy rate provided by the manufacturer are unity of opposites. We also find that it is optimal for the manufacturer to keep the original production plan when the joint-disruption amount is sufficiently small.

This paper addresses a Three-Dimensional Loading Capacitated Vehicle Routing Problem(3L-CVRP) which combines a three-dimensional loading problem and vehicle routing problemin distribution logistics. The problem requires the combinatorial optimization of afeasible loading solution and a successive routing of vehicles to satisfy client demands,where all vehicles must start and terminate at a central depot. In spite of its clearpractical significance in the real world of distribution management, 3L-CVRP in literatureis very limited for its high combinatorial complexity. We solve this problem by a hybridapproach which combines Genetic Algorithm and Tabu Search (GATS). Genetic algorithm isdeveloped for vehicle routing and tabu search for three-dimensional loading, while thesetwo algorithms are integrated for the combinatorial problem. We computationally evaluatethis hybrid genetic algorithm on all publicly available test instances, and obtain newbest solutions for several instances.

In this paper, we develop a supply chain network equilibrium model in which electronic commerce in the presence of both B2B (business-to-business) and B2C (business-to-consumer) transactions, multiperiod decision-making and multicriteria decision-making are integrated. The model consists of three tiers of decision-makers (manufacturers, retailers and consumers at demand markets) who compete within a tier but may cooperate between tiers. Both manufacturers and retailers are concerned with maximization of profit as well as minimization of risk, whereas consumers take both the prices charged by manufacturers and retailers, along with the corresponding costs of transacting, in making their consumption decisions. Increasing relationship levels are assumed to decrease costs of transacting as well as risk costs. Establishing and maintaining these relationship levels incur some costs that have to be borne by the various decision-makers. We study the interaction among different tiers of decision-makers, describe their multicriteria decision-making behavior and derive the optimality conditions as well as the equilibrium conditions which are then shown to satisfy a finite-dimensional variational inequality problem. We then establish qualitative properties of the equilibrium model under some reasonable assumptions and illustrate the model with several numerical examples.

Consider an M/M/1 retrial queue with collisions and working vacation interruption underN-policy. We use a quasi birth and death process to describe the considered system andderive a condition for the stability of the model. Using the matrix-analytic method, weobtain the stationary probability distribution and some performance measures. Furthermore,we prove the conditional stochastic decomposition for the queue length in the orbit.Finally, some numerical examples are presented.

The paper concerns a model of influence in which agents make their decisions on a certainissue. We assume that each agent is inclined to make a particular decision, but due to apossible influence of the others, his final decision may be different from his initialinclination. Since in reality the influence does not necessarily stop after one step, butmay iterate, we present a model which allows us to study the dynamic of influence. Aninnovative and important element of the model with respect to other studies of thisinfluence framework is the introduction of weights reflecting the importance that oneagent gives to the others. These importance weights can be positive, negative or equal tozero, which corresponds to the stimulation of the agent by the ‘weighted’ one, theinhibition, or the absence of relation between the two agents in question, respectively.The exhortation obtained by an agent is defined by the weighted sum of the opinionsreceived by all agents, and the updating rule is based on the sign of the exhortation. Theuse of continuous variables permits the application of differential equations systems tothe analysis of the convergence of agents’ decisions in long-time. We study the dynamic ofsome influence functions introduced originally in the discrete model,e.g., the majority and guru influence functions, but the approachallows the study of new concepts, like e.g. the weighted majorityfunction. In the dynamic framework, we describe necessary and sufficient conditions for anagent to be follower of a coalition, and for a set to be the boss set or the approval setof an agent. equations to the influence model, we recover the results of the discretemodel on on the boss and approval sets for the command games equivalent to some influencefunctions.

This paper aims at describing the way Flow machinery may be used in order to deal with Resource Constrained Project Scheduling Problems (RCPSP). In order to do it, it first introduces the Timed Flow Polyhedron related to a RCPSP instance. Next it states several structural results related to connectivity and to cut management. It keeps on with a description of the way this framework gives rise to a generic Insertion operator, which enables programmers to design greedy and local search algorithms. It ends with numerical experiments.