Polynomial time solutions for scheduling problems on a proportionate flowshop with two competing agents

In scheduling problems with two competing agents, each one of the agents has his own set of jobs and his own objective function, but both share the same processor. The goal is to minimize the value of the objective function of one agent, subject to an upper bound on the value of the objective function of the second agent. In this paper we study two-agent scheduling problems on a proportionate flowshop. Three objective functions of the first agent are considered: minimum maximum cost of all the jobs, minimum total completion time, and minimum number of tardy jobs. For the second agent, an upper bound on the maximum allowable cost is assumed. We introduce efficient polynomial time solution algorithms for all cases.     

Fast approximation algorithms for bi-criteria scheduling with machine assignment costs

We consider parallel machine scheduling problems where the processing of the jobs on the machines involves two types of objectives. The first type is one of two classical objective functions in scheduling theory: either the total completion time or the makespan. The second type involves an actual cost associated with the processing of a specific job on a given machine; each job-machine combination may have a different cost. Two bi-criteria scheduling problems are considered: (1) minimize the maximum machine cost subject to the total completion time being at its minimum, and (2) minimize the total machine cost subject to the makespan being at its minimum. Since both problems are strongly NP-hard, we propose fast heuristics and establish their worst-case performance bounds.     

A note on two-agent scheduling on an unbounded parallel-batching machine with makespan and maximum lateness objectives

This paper studies the two-agent scheduling on an unbounded parallel-batching machine. In the problem, there are two agents A and B with each having their own job sets. The jobs of a common agent can be processed in a common batch. Moreover, each agent has an objective function to be minimized. The objective function of agent A is the makespan of his jobs and the objective function of agent B is maximum lateness of his jobs. Yazdani Sabouni and Jolai [M.T. Yazdani Sabouni, F. Jolai, Optimal methods for batch processing problem with makespan and maximum lateness objectives, Appl. Math. Model. 34 (2010) 314–324] presented a polynomial-time algorithm for the problem to minimize a positive combination of the two agents’ objective functions. Unfortunately, their algorithm is incorrect. We then dwell on the problem and present a polynomial-time algorithm for finding all Pareto optimal solutions of this two-agent parallel-batching scheduling problem.     

On a class of quadratic programs

This paper considers a class of quadratic programs where the constraints ae linear and the objective is a product of two linear functions. Assuming the two linear factors to be non-negative, maximization and minimization cases are considered. Each case is analyzed with the help of a bicriteria linear program obtained by replacing the quadratic objective with the two linear functions. Global minimum (maximum) is attained at an efficient extreme point (efficient point) of the feasible set in the solution space and corresponds to an efficient extreme point (efficient point) of the feasible set in the bicriteria space. Utilizing this fact and certain other properties, two finite algorithms, including validations are given for solving the respective problems. Each of these, essentially, consists of solving a sequence of linear programs. Finally, a method is provided for relaxing the non-negativity assumption on the two linear factors of the objective function.     

Combination of MCDM and covering techniques in a hierarchical model for facility location: A case study

In this paper, locating some warehouses as distribution centers (DCs) in a real-world military logistics system will be investigated. There are two objectives: finding the least number of DCs and locating them in the best possible locations. The first objective implies the minimum cost of locating the facilities and the latter expresses the quality of the DCs locations, which is evaluated by studying the value of appropriate attributes affecting the quality of a location. Quality of a location depends on a number of attributes; so the value of each location is determined by using Multi Attribute Decision Making models, by considering the feasible alternatives, the related attributes and their weights according to decision maker’s (DM) point of view. Then, regarding the obtained values and the minimum number of DCs, the two objective functions are formed. Constraints imposed on these two objectives cover all centers, which must be supported by the DCs. Using Multiple Objective Decision Making techniques, the locations of DCs are determined. In the final phase, we use a simple set partitioning model to assign each supported center to only one of the located DCs.     

Multi-objective multi-item solid transportation problem in fuzzy environment

A multi-objective multi-item solid transportation problem with fuzzy coefficients for the objectives and constraints, is modeled and then solved by two different methods. A defuzzification method based on fuzzy linear programming is applied for fuzzy supplies, demands and conveyance capacities, including the condition that both total supply and conveyance capacity must not fall below the total demand. First, expected values of the fuzzy objective functions are considered to derive crisp values. Another method based on the concept of “minimum of fuzzy number” is applied for the objective functions that yields fuzzy values instead of particular crisp values for the fuzzy objectives. Fuzzy programming technique and global criterion method are applied to derive optimal compromise solutions of multi-objectives. A numerical example is solved using above mentioned methods and corresponding results are compared.     

Augmented Lagrangian functions for constrained optimization problems

In this paper, in order to obtain some existence results about solutions of the augmented Lagrangian problem for a constrained problem in which the objective function and constraint functions are noncoercive, we construct a new augmented Lagrangian function by using an auxiliary function. We establish a zero duality gap result and a sufficient condition of an exact penalization representation for the constrained problem without the coercive or level-bounded assumption on the objective function and constraint functions. By assuming that the sequence of multipliers is bounded, we obtain the existence of a global minimum and an asymptotically minimizing sequence for the constrained optimization problem.     

Building models of values

To achieve a set of objectives, whether they are made explicit or not, is the entire intent of decisionmaking. When they are explicitly stated, the objectives are often quantified with an objective function. Because of its critical role for decisionmaking, the objective function should be developed from first principles, sound logic, reasoned judgments, and carefully acquired consistent data. Unfortunately, in practice many objective functions are hastily chosen froma process that can at best be described as arbitrary. This paper presents a better alternative for developing the objective function, namely to construct it from a quality modelling effort.     

关于条件极值的两点思考

认为现行高等数学教材关于多元函数条件极值的处理存在值得商榷之处.实例分析多元函数条件极值的拉格朗日乘数法和代人法.指出它们都必须受条件函数梯度非零的限制.利用已知目标函数和条件函数的一阶、二阶偏导数可以判定拉格朗日乘数法所得出的可能极值点处是取极大值还是极小值.由此可得判定条件极值的一个充分条件.     

An interactive weight space reduction procedure for nonlinear multiple objective mathematical programming

To make a decision that is defined by multiple, conflicting objectives it is necessary to know the relative importance of the different objectives. In this paper we present an interactive method and the underlying theory for solving multiple objective mathematical programming problems defined by a convex feasible region and concave, continuously differentiable objective functions. The relative importance of the different objectives for a decision maker is elicited by using binary comparisons of objective function vectors. The method is cognitively easy to use and in test problems has rapidly converged to an optimal solution.     

An exact method for computing the nadir values in multiple objective linear programming

In this paper we propose a new method to determine the exact nadir (minimum) criterion values over the efficient set in multiple objective linear programming (MOLP). The basic idea of the method is to determine, for each criterion, the region of the weight space associated with the efficient solutions that have a value in that criterion below the minimum already known (by default, the minimum in the payoff table). If this region is empty, the nadir value has been found. Otherwise, a new efficient solution is computed using a weight vector picked from the delimited region and a new iteration is performed. The method is able to find the nadir values in MOLP problems with any number of objective functions, although the computational effort increases significantly with the number of objectives. Computational experiments are described and discussed, comparing two slightly different versions of the method.     

Combined Discrete-event Simulation and Ant Colony Optimisation Approach for Selecting Optimal Screening Policies for Diabetic Retinopathy

In this paper we present the first application to a healthcare problem of discrete-event simulation (DES) embedded in an ant colony optimisation (ACO) model. We are concerned with choosing optimal screening policies for retinopathy, a sight-threatening complication of diabetes. The early signs of retinopathy can be detected by screening before the patient is aware of symptoms, and blindness prevented by laser treatment. In this paper we describe the methodology used to combine the purpose-written DES model with the ACO algorithm. We simulate the effects of different screening strategies on a population of diabetic patients, and compare them in terms of two objective functions: Min C/E, cost-effectiveness (minimum incremental cost per year of sight saved, compared with a no-screening baseline) and Max E, maximum effectiveness (years of sight saved). We describe how ACO is used to optimise these two objectives, and discuss the issues involved in optimising stochastic variables. We present results for a range of different assumptions and scenarios about the format of screening programmes, using realistic data, and make policy recommendations on the basis of our findings.     

A parametric successive underestimation method for convex multiplicative programming problems

This paper addresses itself to the algorithm for minimizing the product of two nonnegative convex functions over a convex set. It is shown that the global minimum of this nonconvex problem can be obtained by solving a sequence of convex programming problems. The basic idea of this algorithm is to embed the original problem into a problem in a higher dimensional space and to apply a branch-and-bound algorithm using an underestimating function. Computational results indicate that our algorithm is efficient when the objective function is the product of a linear and a quadratic functions and the constraints are linear. An extension of our algorithm for minimizing the sum of a convex function and a product of two convex functions is also discussed.     

On assignment functions

We define a class of functions called assignment functions, one of which is the permanent function. These functions evaluated at matrices of 0's and 1's are shown to be of applied and combinational interest. We define assignment polytopes which generalize the classical assignment polytope and use them to obtain bounds for the assignment function. We propose the determination of the minimum and maximum value of an assignment function on its corresponding assignment polytope and conjecture that the maximum value is 1. A natural conjecture for the minimum value is shown to be false. The minimum and maximum value are determined for special assignment functions.     

On a Global Optimization Algorithm for Bivariate Smooth Functions

The problem of approximating the global minimum of a function of two variables is considered. A method is proposed rooted in the statistical approach to global optimization. The proposed algorithm partitions the feasible region using a Delaunay triangulation. Only the objective function values are required by the optimization algorithm. The asymptotic convergence rate is analyzed for a class of smooth functions. Numerical examples are provided.     

Sustainable production technologies which take into account environmental constraints

We formulate and study a multiobjective programming approach for production processes which implements suitable constraints on pollutant emissions. We consider two alternative optimization problems: (a) minimum pollution risk; (b) maximum expected return. For each pollutant, we define three different contamination levels: (a) the desirable or the target pollution level, (b) the alarm (warning or critical) level and (c) the maximum admissible (acceptable) level, and introduce penalties proportional to the amounts of pollutants that exceed these levels. The objective function of the minimum pollution risk problem is not smooth since it contains positive parts of some affine functions, resulting in mathematical difficulties, which can be solved by formulating an alternative linear programming model, which makes use of additional variables and has the same solutions as the initial problem. We investigate various particular cases and analyze a numerical example for a textile plant.     

On the Definition of a Minimum in Parameter Optimization

For the unconstrained minimization of an ordinary function, there are essentially two definitions of a minimum. The first involves the inequality \(\le \), and the second, the inequality <. The purpose of this Forum is to discuss the consequences of using these definitions for finding local and global minima of the constant objective function. The first definition says that every point on the constant function is a local minimum and maximum, as well as a global minimum and maximum. This is not a rational result. On the other hand, the second definition says that the constant function cannot be minimized in an unconstrained problem. It must be treated as a constrained problem where the constant function is the lower boundary of the feasible region. This is a rational result. As a consequence, it is recommended that the standard definition (\(\le \)) for a minimum be replaced by the second definition (<).     

Problems and methods with multiple objective functions

LetA be a set of feasible alternatives or decisions, and supposen different indices, measures, or objectives are associated with each possible decision ofA. How can a “best” feasible decision be made? What methods can be used or experimented with to reach some decision? The purpose of this paper is to attempt a synthesis of the main approaches to this problem which have been studied to date. Four different classes of approaches are distinguished: (1) aggregation of multiple objective functions into a unique function defining a complete preference order; (2) progressive definition of preference together with exploration of the feasible set; (3) definition of a partial order stronger than the product of then complete orders associated with then objective functions; and (4) maximum reduction of uncertainty and incomparability.     

An interactive satisficing method based on alternative tolerance for fuzzy multiple objective optimization

An interactive satisficing method based on alternative tolerance is proposed for fuzzy multiple objective optimization. The new tolerances of the dissatisficing objectives are generated using an auxiliary programming problem. According to the alternative tolerant limits, either the membership functions are changed, or the objective constraints are added. The lexicographic two-phase programming is implemented to find the final solution. The results of the dissatisficing objectives are iteratively improved. The presented method not only acquires the efficient or weak efficient solution of all the objectives, but also satisfies the progressive preference of decision maker. Numerical examples show its power.     

Setting targets for surrogate-based optimization

In the context of surrogate-based optimization (SBO), most designers have still very little guidance on when to stop and how to use infill measures with target requirements (e.g., one-stage approach for goal seeking and optimization); the reason: optimum estimates independent of the surrogate and optimization strategy are seldom available. Hence, optimization cycles are typically stopped when resources run out (e.g., number of objective function evaluations/time) or convergence is perceived, and targets are empirically set which may affect the effectiveness and efficiency of the SBO approach. This work presents an approach for estimating the minimum (target) of the objective function using concepts from extreme order statistics which relies only on the training data (sample) outputs. It is assumed that the sample inputs are randomly distributed so the outputs can be considered a random variable, whose density function is bounded (a, b), with the minimum (a) as its lower bound. Specifically, an estimate of the minimum (a) is obtained by: (i) computing the bounds (using training data and the moment matching method) of a selected set of analytical density functions (catalog), and (ii) identifying the density function in the catalog with the best match to the sample outputs distribution and corresponding minimum estimate (a). The proposed approach makes no assumption about the nature of the objective functions, and can be used with any surrogate, and optimization strategy even with high dimensional problems. The effectiveness of the proposed approach was evaluated using a compact catalog of Generalized Beta density functions and well-known analytical optimization test functions, i.e., F2, Hartmann 6D, and Griewangk 10D and in the optimization of a field scale alkali-surfactant-polymer enhanced oil recovery process. The results revealed that: (a) the density function (from a catalog) with the best match to a function outputs distribution, was the same for both large and reduced samples, (b) the true optimum value was always within a 95% confidence interval of the estimated minimum distribution, and (c) the estimated minimum represents a significant improvement over the present best solution and an excellent approximation of the true optimum value.