Workforce scheduling with multiple objectives

In workforce scheduling, the optimal schedule has traditionally been determined by minimizing the cost of labor subject to an acceptable service level, which is defined as the percentage of customers served within a predetermined time interval. We propose an alternative multidimensional paradigm, where cost minimization and service level maximization are considered simultaneously, together with other, complementary criteria. The ultimate goal of the proposed approach is to open a broader workforce scheduling paradigm that incorporates service quality into the analysis and provides the possibility to study the interaction between cost and service quality. Furthermore, the approach enables us to avoid strong assumptions. An example with real-world, empirical demand data is provided.     

Fuzzy bilevel programming with multiple objectives and cooperative multiple followers

Classic bilevel programming deals with two level hierarchical optimization problems in which the leader attempts to optimize his/her objective, subject to a set of constraints and his/her follower’s solution. In modelling a real-world bilevel decision problem, some uncertain coefficients often appear in the objective functions and/or constraints of the leader and/or the follower. Also, the leader and the follower may have multiple conflicting objectives that should be optimized simultaneously. Furthermore, multiple followers may be involved in a decision problem and work cooperatively according to each of the possible decisions made by the leader, but with different objectives and/or constraints. Following our previous work, this study proposes a set of models to describe such fuzzy multi-objective, multi-follower (cooperative) bilevel programming problems. We then develop an approximation Kth-best algorithm to solve the problems.     

Using multiple objectives to approximate normative models

This paper discusses the rationale for the use of additive models involving multiple objectives as approximations to normative analyses. Experience has shown us that organizations often evaluate important decisions with multiple objective models rather than reducing all aspects of the problem to a single criterion, dollars, as many normative economic models prescribe. We justify this practice on two grounds: managers often prefer to think about a problem in terms of several dimensions and a multiple objective model may provide an excellent approximation to the more complex normative model. We argue that a useful analysis based on a multiple objective model will fulfill both conditions—it will provide insights for the decision maker as well as a good approximation to the normative model. We report several real-world examples of managers using multiple objective models to approximate such normative models as the risk-adjusted net present value and the value of information models. The agreement between the approximate models and the normative models is shown to be quite good. Next, we cite a portion of the behavioral decision theory literature which establishes that linear models of multiple attributes provide quite robust approximations to individual decision-making processes. We then present more general theoretical and empirical results which support our contention that linear multiple attribute models can provide good approximations to more complex models.     

On spanning tree problems with multiple objectives

We investigate two versions of multiple objective minimum spanning tree problems defined on a network with vectorial weights. First, we want to minimize the maximum ofQ linear objective functions taken over the set of all spanning trees (max-linear spanning tree problem, ML-ST). Secondly, we look for efficient spanning trees (multi-criteria spanning tree problem, MC-ST).Problem ML-ST is shown to be NP-complete. An exact algorithm which is based on ranking is presented. The procedure can also be used as an approximation scheme. For solving the bicriterion MC-ST, which in the worst case may have an exponential number of efficient trees, a two-phase procedure is presented. Based on the computation of extremal efficient spanning trees we use neighbourhood search to determine a sequence of solutions with the property that the distance between two consecutive solutions is less than a given accuracy.Partially supported by Deutsche Forschungsgemeinschaft and HCº Contract no. ERBCHRXCT 930087.Partially supported by Alexander von Humboldt-Stiftung.     

Exploring the interface between hierarchies,multiple objectives and fuzzy sets

The complexity of experience acquired through our senses and as interpreted by our mind, is fuzzy and must remain so as long as the meaning of things change as they are embedded in larger or different contexts to relate them to new ideas and new experiences. Here we give a method for measuring the relativity of fuzziness by structuring the functions of a system hierarchically in a multiple objective framework. The method is based on computing the principal eigenvector of a positive matrix with reciprocal entries (i.e., a_ji = 1/a_ij). The eigenvector provides an estimate for an (assumed) underlying ratio scale. For a single property the scale provides a measure of the grade of membership of elements in a fuzzy set according to that property and the departure of the eigenvalue from the dimension of the matrix serves as a measure of departure from consistency. For a number of properties, the principle of hierarchical composition enables us to compose the eigenvectors into a priority vector which measures the fuzziness of the elements in the lowest level of the hierarchy with respect to the relative dominance of the purposes or properties represented in the hierarchy.     

Production and marketing decisions with multiple objectives in a competitive environment

This paper presents an application of the mathematical program which has been called the Fritz John problem to a situation in applied economics. A model is presented which enables a firm to maximize profit, subject to constraints on maintenance of market share in the face of collusive action by competitors and subject to resource constraints. An example problem is formulated and solved.The authors wish to acknowledge comments and suggestions offered by J. W. Blankenship and R. E. Kuenne.     

On the criterion vectors of lines of portfolio selection with multiple quadratic and multiple linear objectives

As the research for portfolio selection evolves, traditional models and models with one quadratic objective and multiple linear objectives are being solved. In this paper, I propose models with multiple quadratic and multiple linear objectives. Due to the difficulty involved, I study the new models by lines in decision space, analyze the criterion vectors of the lines by projection, and approximate the nondominated sets by the criterion vectors. As an illustration, I extend Merton’s portfolio selection model, propose algorithms to approximate the nondominated sets by the criterion vectors of portfolios with cardinality 3 and then K, and demonstrate the number of the criterion vectors.     

A robust approach for scheduling in hospitals using multiple objectives

Scheduling in hospitals is a challenging task and stochastic influences have a major impact on the final schedule. Therefore, uncertainties of treatment durations and of emergency arrivals have to be taken into account explicitly. In order to avoid re-scheduling we integrate information on stochastic parameters into a scenario-based mixed-integer optimization model. Besides, we focus on different stakeholders’ objectives that are simultaneously considered within a multi-criteria optimization model. Individually optimal solutions are likely to differ and the overall aim is to identify a good and acceptable compromise solution. The presented approach is based on fuzzy sets and merges the interests of several stakeholders. Different schedules are calculated and later on evaluated with randomly generated scenarios for surgery times and emergencies. The resulting objective function values are close to the individually optimal solutions. Finally, the schedules lead to a high rate of utilization and a low amount of overtime.     

Linear bilevel programs with multiple objectives at the upper level

Bilevel programming has been proposed for dealing with decision processes involving two decision makers with a hierarchical structure. They are characterized by the existence of two optimization problems in which the constraint region of the upper level problem is implicitly determined by the lower level optimization problem. Focus of the paper is on general bilevel optimization problems with multiple objectives at the upper level of decision making. When all objective functions are linear and constraints at both levels define polyhedra, it is proved that the set of efficient solutions is non-empty. Taking into account the properties of the feasible region of the bilevel problem, some methods of computing efficient solutions are given based on both weighted sum scalarization and scalarization techniques. All the methods result in solving linear bilevel problems with a single objective function at each level.     

Pyramidal values

We propose and analyze a new type of values for cooperative TU-games, which we call pyramidal values. Assuming that the grand coalition is sequentially formed, and all orderings are equally likely, we define a pyramidal value to be any expected payoff in which the entrant player receives a salary, and the rest of his marginal contribution to the just formed coalition is distributed among the incumbent players. We relate the pyramidal-type sharing scheme we propose with other sharing schemes, and we also obtain some known values by means of this kind of pyramidal procedures. In particular, we show that the Shapley value can be obtained by means of an interesting pyramidal procedure that distributes nonzero dividends among the incumbents. As a result, we obtain an alternative formulation of the Shapley value based on a measure of complementarity between two players. Finally, we introduce the family of proportional pyramidal values, in which an incumbent receives a dividend in proportion to his initial investment, measured by means of his marginal contribution.     

Sur les tours localement cyclotomiques

For a given number field K and any prime l\ell we construct an increasing sequence of l\ell -extensions K_n of K which are locally cyclotomic over K. We give various criterious of finiteness or non-finiteness of this l\ell -tower and we characterise the number fields which have such a finite tower in terms of Iwasawa theory.     

A heuristic algorithm for a dial-a-ride problem with time windows,multiple capacities,and multiple objectives

The paper describes a system for the solution of a static dial-a-ride routing and scheduling problem with time windows (DARPTW). The problem statement and initialization of the development project was made by the Copenhagen Fire-Fighting Service (CFFS). The CFFS needed a new system for scheduling elderly and disabled persons, involving about 50.000 requests per year. The problem is characterized by, among other things, multiple capacities and multiple objectives. The capacities refer to the fact that a vehicle may be equipped with e.g. normal seats, children seats or wheel chair places. The objectives relate to a number of concerns such as e.g. short driving time, high vehicle utilization or low costs. A solution algorithm REBUS based on an insertion heuristics was developed. The algorithm permits in a flexible way weighting of the various goals such that the solution reflects the user's preferences. The algorithm is implemented in a dynamic environment intended for on-line scheduling. Thus, a new request for service is treated in less than 1 second, permitting an interactive user interface.     

Pareto quantity flexibility contracts for a supply chain under multiple objectives

We analyse a decentralized supply chain consisting of a supplier and a retailer. The terms of trade between the two agents are specified by a quantity flexibility (QF) contract. We first identify the Pareto QF contracts for the supply chain where each agent adopts a satisficing objective, that is, to maximize the probability of achieving his/her predetermined target profit. It is shown that to coordinate such a supply chain, QF contracts have to degenerate into wholesale price (WP) contracts. This provides an additional justification for the popularity of WP contracts besides their simplicities and lower administration costs. Next, we consider the supply chain where each agent adopts multiple objectives, namely the satisficing objective and the objective of expected profit maximization (EPM). It is shown that there always exist QF contracts that coordinate the supply chain under the objective of EPM and are simultaneously Pareto optimal for the satisficing objective.     

Careful usage of pessimistic values is needed in multiple objectives optimization

Attention is drawn to the fact that so-called pessimistic values are not lower bounds for the objective function values on the efficient solution set. Two counterexamples, to stress this point, are presented.     

Reoptimization of minimum and maximum traveling salesman's tours

In this paper, reoptimization versions of the traveling salesman problem (TSP) are addressed. Assume that an optimum solution of an instance is given and the goal is to determine if one can maintain a good solution when the instance is subject to minor modifications. We study the case where nodes are inserted in, or deleted from, the graph. When inserting a node, we show that the reoptimization problem for MinTSP is approximable within ratio 4/3 if the distance matrix is metric. We show that, dealing with metric MaxTSP, a simple heuristic is asymptotically optimum when a constant number of nodes are inserted. In the general case, we propose a 4/5-approximation algorithm for the reoptimization version of MaxTSP.