A heuristic approach to bicriteria scheduling

We consider the problem of sequencing jobs on a single machine while minimizing a nondecreasing function of two criteria. We develop a heuristic procedure that quickly finds a good solution for bicriteria scheduling. The procedure is based on using several arcs in the criterion space that are representative of the possible locations of nondominated solutions. By sampling a small number of points on these arcs, a promising point is identified in the criterion space for each arc. An efficient sequence in the neighborhood of each of the promising points is found and the best of these efficient sequences is selected as the heuristic solution. We implement the procedure for two different bicriteria scheduling problems: (i) minimizing total flowtime and maximum tardiness and (ii) minimizing total flowtime and maximum earliness. The computational experience on a wide variety of problem instances show that the heuristic approach is very robust and yields good solutions. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 777–789, 1999     

Bicriteria multiresource generalized assignment problem

In this study, we consider a bicriteria multiresource generalized assignment problem. Our criteria are the total assignment load and maximum assignment load over all agents. We aim to generate all nondominated objective vectors and the corresponding efficient solutions. We propose several lower and upper bounds and use them in our optimization and heuristic algorithms. The computational results have shown the satisfactory behaviors of our approaches. © 2014 Wiley Periodicals, Inc. Naval Research Logistics, 61: 621–636, 2014     

Extending the MAD portfolio optimization model to incorporate downside risk aversion

A mathematical model of portfolio optimization is usually represented as a bicriteria optimization problem where a reasonable tradeoff between expected rate of return and risk is sought. In a classical Markowitz model, the risk is measured by a variance, thus resulting in a quadratic programming model. As an alternative, the MAD model was developed by Konno and Yamazaki, where risk is measured by (mean) absolute deviation instead of a variance. The MAD model is computationally attractive, since it is easily transformed into a linear programming problem. An extension to the MAD model proposed in this paper allows us to measure risk using downside deviations, with the ability to penalize larger downside deviations. Hence, it provides for better modeling of risk averse preferences. The resulting m‐MAD model generates efficient solutions with respect to second degree stochastic dominance, while at the same time preserving the simplicity and linearity of the original MAD model. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 185–200, 2001     

Interactive solution of bi-criteria mathematical programs

In this paper, we develop efficient interactive methods for the solution of bicriteria nonlinear programming problems. The methods do not require trade-off information from the decision maker, pose less cognitive burden and converge to the “best compromise solution” fast. Two methods, called the paired comparison method and comparative trade-off method, are presented with examples. A real application of the interactive method to a bicriteria problem that arose in the planning of the cardiovascular disease control program in the U.S. Air Force is also presented.     

Bounded flexibility in days‐on and days‐off scheduling

This article presents a flexible days‐on and days‐off scheduling problem and develops an exact branch and price (B&P) algorithm to find solutions. The main objective is to minimize the size of the total workforce required to cover time‐varying demand over a planning horizon that may extend up to 12 weeks. A new aspect of the problem is the general restriction that the number of consecutive days on and the number of consecutive days off must each fall within a predefined range. Moreover, the total assignment of working days in the planning horizon cannot exceed some maximum value. In the B&P framework, the master problem is stated as a set covering‐type problem whose columns are generated iteratively by solving one of three different subproblems. The first is an implicit model, the second is a resource constrained shortest path problem, and the third is a dynamic program. Computational experiments using both real‐word and randomly generated data show that workforce reductions up to 66% are possible with highly flexible days‐on and days‐off patterns. When evaluating the performance of the three subproblems, it was found that each yielded equivalent solutions but the dynamic program proved to be significantly more efficient. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 678–701, 2013     

Note: Bicriteria scheduling for minimizing flow time and maximum tardiness

We consider the bicriteria problem of minimizing total flow time and maximum tardiness penalties for a given set of jobs on a single machine. We develop an algorithm that finds the optimal schedule for any given monotonic function of the two criteria by generating only a small subset of the efficient schedules.     

Multiobjective fractional programming duality theory

Results of Geoffrion for efficient and properly efficient solutions of multiobjective programming problems are extended to multiobjective fractional programming problems. Duality relationships are given for these problems where the functions are generalized convex or invex.     

The enumeration of all efficient solutions for a linear multiple-objective transportation problem

An algorithm is presented by which the set of all efficient solutions for a linear multiple-objective transportation problem can be enumerated. First the algorithm determines an initial efficient basic solution. In a second step all efficient basic solutions are enumerated. Finally, the set of all efficient solutions is constructed as a union of a minimal number of convex sets of efficient solutions. The algorithm is illustrated by a numerical example.     

Bicriteria product design optimization: An efficient solution procedure using AND/OR trees

Competitive imperatives are causing manufacturing firms to consider multiple criteria when designing products. However, current methods to deal with multiple criteria in product design are ad hoc in nature. In this paper we present a systematic procedure to efficiently solve bicriteria product design optimization problems. We first present a modeling framework, the AND/OR tree, which permits a simplified representation of product design optimization problems. We then show how product design optimization problems on AND/OR trees can be framed as network design problems on a special graph—a directed series‐parallel graph. We develop an enumerative solution algorithm for the bicriteria problem that requires as a subroutine the solution of the parametric shortest path problem. Although this parametric problem is hard on general graphs, we show that it is polynomially solvable on the series‐parallel graph. As a result we develop an efficient solution algorithm for the product design optimization problem that does not require the use of complex and expensive linear/integer programming solvers. As a byproduct of the solution algorithm, sensitivity analysis for product design optimization is also efficiently performed under this framework. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 574–592, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10031     

Scheduling a maintenance activity on parallel identical machines

We study a problem of scheduling a maintenance activity on parallel identical machines, under the assumption that all the machines must be maintained simultaneously. One example for this setting is a situation where the entire system must be stopped for maintenance because of a required electricity shut‐down. The objective is minimum flow‐time. The problem is shown to be NP‐hard, and moreover impossible to approximate unless P = NP. We introduce a pseudo‐polynomial dynamic programming algorithm, and show how to convert it into a bicriteria FPTAS for this problem. We also present an efficient heuristic and a lower bound. Our numerical tests indicate that the heuristic provides in most cases very close‐to‐optimal schedules. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009     

An algorithm for the solution of a location problem with metric constraints

In many location problems, the solution is constrained to lie within a closed set. In this paper, optimal solutions to a special type of constrained location problem are characterized. In particular, the location problem with the solution constrained to be within a maximum distance of each demand point is considered, and an algorithm for its solution is developed and discussed.     

An interactive optimization system for bulk-cargo ship scheduling

This article considers the efficient scheduling of a fleet of ships engaged in pickup and delivery of bulk cargoes. Our optimization system begins by generating a menu of candidate schedules for each ship. This menu can contain all feasible solutions, which guarantees we will find an optimal solution or can be heuristically limited to contain only those schedules likely to be in an optimal solution. The problem of choosing from this menu an optimal schedule for the fleet is formulated as a set-packing problem and solved with a dual algorithm. Computational experience is presented based on real data obtained from the Military Sealift Command of the U. S. Navy. Run times for this data were reasonable and solutions were generated with the potential of saving up to about $30 million per year over the manual system currently in place. We also describe a color-graphics interface developed to facilitate interaction with the optimization system.     

Generating Pareto‐optimal boundary points in multiparty negotiations using constraint proposal method

In this paper a constraint proposal method is developed for computing Pareto‐optimal solutions in multiparty negotiations over continuous issues. Constraint proposal methods have been previously studied in a case where the decision set is unconstrained. Here we extend the method to situations with a constrained decision set. In the method the computation of the Pareto‐optimal solutions is decentralized so that the DMs do not have to know each others' value functions. During the procedure they have to indicate their optimal solutions on different sets of linear constraints. When the optimal solutions coincide, the common optimum is a candidate for a Pareto‐optimal point. The constraint proposal method can be used to generate either one Pareto‐optimal solution dominating the status quo solution or several Pareto‐optimal solutions. In latter case a distributive negotiation among the efficient points can be carried out afterwards. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 210–225, 2001     

Locating facilities in three-dimensional space by convex programming

We consider the problem of simultaneously locating any number of facilities in three-dimensional Euclidean space. The criterion to be satisfied is that of minimizing the total cost of some activity between the facilities to be located and any number of fixed locations. Any amount of activity may be present between any pair of the facilities themselves. The total cost is assumed to be a linear function of the inter-facility and facility-to-fixed locations distances. Since the total cost function for this problem is convex, a unique optimal solution exists. Certain discontinuities are shown to exist in the derivatives of the total cost function which previously has prevented the successful use of gradient computing methods for locating optimal solutions. This article demonstrates the use of a created function which possesses all the necessary properties for ensuring the convergence of first order gradient techniques and is itself uniformly convergent to the actual objective function. Use of the fitted function and the dual problem in the case of constrained problems enables solutions to be determined within any predetermined degree of accuracy. Some computation results are given for both constrained and unconstrained problems.     

A manpower planning/capital budgeting model (MAPCAB)

A deterministic resource allocation model is developed to optimize defense effectiveness subject to budget, manpower, and risk constraints. The model consists of two major submodels connected by a heuristic. The first is a mathematical program which optimizes the multiperiod weapon mix subject to the constraint set. The second is a manpower supply model based on a transition matrix in which individual transitions are functions of personnel related budgets and historical transition rates. The heuristic marries the submodels through an iterative process leading to improved solutions. An example is provided which demonstrates how systems are undercosted and overprocured if manpower supply is not properly reflected relative to manpower demand.     

Determination of efficient points in multiple-objective location problems

This article is devoted to an MCDM problem connected with locational analysis. The MCDM problem can be formulated so as to minimize the distance between a facility and a given set of points. The efficient points of this problem are candidates for optimal solutions to many location problems. We propose an algorithm to find all efficient points when distance is measured by any polyhedral norm.     

THE CREATION OF THE ICC

The implications for African states of the recently created International Criminal Court should be carefully considered. There are far-reaching limitations placed on the ICC's jurisdictional scheme, both temporally as well as by the preconditions to the exercise of jurisdiction in the form of territoriality and nationality. The Court's powers may also be constrained out of deference to the grant of an internationally acceptable amnesty, and national courts may be constrained to recognise immunities from prosecution for high-ranking officials. These limitations need to be properly understood so that the ICC can be effectively utilised by African States to declare and act upon their commitment to the principle of individual criminal liability for those responsible for the most serious crimes.     

The minmax multidimensional knapsack problem with application to a chance‐constrained problem

In this paper we present a new combinatorial problem, called minmax multidimensional knapsack problem (MKP), motivated by a military logistics problem. The logistics problem is a two‐period, two‐level, chance‐constrained problem with recourse. We show that the MKP is NP‐hard and develop a practically efficient combinatorial algorithm for solving it. We also show that under some reasonable assumptions regarding the operational setting of the logistics problem, the chance‐constrained optimization problem is decomposable into a series of MKPs that are solved separately. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

An interactive paired comparison method for bicriterion integer programming

This article proposes an interactive paired comparison region elimination method for bicriterion integer mathematical programming problems. The new method isolates the best compromise solution by successively evaluating a pair of associated supported non-dominated solutions. The efficiency of the method is tested by solving randomly generated problems based on varying shapes of efficient frontiers. When compared with the existing branch-and-bound method, the method was effective in reducing the burden on the decision maker. © 1994 John Wiley & Sons, Inc.     

Scheduling to minimize the total compression and late costs

We consider a single-machine scheduling model in which the job processing times are controllable variables with linear costs. The objective is to minimize the sum of the cost incurred in compressing job processing times and the cost associated with the number of late jobs. The problem is shown to be NP-hard even when the due dates of all jobs are identical. We present a dynamic programming solution algorithm and a fully polynomial approximation scheme for the problem. Several efficient heuristics are proposed for solving the problem. Computational experiments demonstrate that the heuristics are capable of producing near-optimal solutions quickly. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 67–82, 1998