Single machine stochastic JIT scheduling problem subject to machine breakdowns

In this paper we research the single machine stochastic JIT scheduling problem subject to the machine breakdowns for preemptive-resume and preemptive-repeat.The objective function of the problem is the sum of squared deviations of the job-expected completion times from the due date.For preemptive-resume,we show that the optimal sequence of the SSDE problem is V-shaped with respect to expected processing times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.We discuss the difference between the SSDE problem and the ESSD problem and show that the optimal solution of the SSDE problem is a good approximate optimal solution of the ESSD problem,and the optimal solution of the SSDE problem is an optimal solution of the ESSD problem under some conditions.For preemptive-repeat,the stochastic JIT scheduling problem has not been solved since the variances of the completion times cannot be computed.We replace the ESSD problem by the SSDE problem.We show that the optimal sequence of the SSDE problem is V-shaped with respect to the expected occupying times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.A new thought is advanced for the research of the preemptive-repeat stochastic JIT scheduling problem.     

A novel neural network based on NCP function for solving constrained nonconvex optimization problems

This article presents a novel neural network (NN) based on NCP function for solving nonconvex nonlinear optimization (NCNO) problem subject to nonlinear inequality constraints. We first apply the p‐power convexification of the Lagrangian function in the NCNO problem. The proposed NN is a gradient model which is constructed by an NCP function and an unconstrained minimization problem. The main feature of this NN is that its equilibrium point coincides with the optimal solution of the original problem. Under a proper assumption and utilizing a suitable Lyapunov function, it is shown that the proposed NN is Lyapunov stable and convergent to an exact optimal solution of the original problem. Finally, simulation results on two numerical examples and two practical examples are given to show the effectiveness and applicability of the proposed NN. © 2015 Wiley Periodicals, Inc. Complexity 21: 130–141, 2016     

Aanwendung des erweiterungsprinzips zur lösung konkayer optimierungsaufgaben

For the problem of minimizing a concave function over a convex polyedral-set an algorithm is given, which is based on the extension principle developed by Schoch. This algorithm yields after a finite number of steps an exact optimal solution of the problem. On the other hand one can find out throughout the algorithm an approximate optimal solution with any given precision.     

An Algorithm for Solving Optimization Problems with One Linear Objective Function and Finitely Many Constraints of Fuzzy Relation Inequalities

An optimization model with one linear objective function and fuzzy relation equation constraints was presented by Fang and Li (1999) as well as an efficient solution procedure was designed by them for solving such a problem. A more general case of the problem, an optimization model with one linear objective function and finitely many constraints of fuzzy relation inequalities, is investigated in this paper. A new approach for solving this problem is proposed based on a necessary condition of optimality given in the paper. Compared with the known methods, the proposed algorithm shrinks the searching region and hence obtains an optimal solution fast. For some special cases, the proposed algorithm reaches an optimal solution very fast since there is only one minimum solution in the shrunk searching region. At the end of the paper, two numerical examples are given to illustrate this difference between the proposed algorithm and the known ones.     

Dynamic programming and the Hamilton-Jacobi method of classical mechanics

The conventional dynamic programming method for analytically solving a variational problem requires the determination of a particular solution, the optimal value function or return function, of the fundamental partial differential equation. Associated with it is another function, the optimal policy function. At each point, this function yields the value of the slope of the optimal curve to that point (or from that point, depending on the method of solution). The optimal curve itself can then be found by integration. In this paper, dynamic programming concepts and principles are used to develop two alternatives to the conventional method of solution. In the first method, a particular solution of two simultaneous partial differential equations is used to generate optimal curves by differentiations and solution of simultaneous equations. In the second method, any solution of the fundamental equation containing an appropriate number of arbitrary constants is sought. It is shown how such a function yields directly, by differentiations and solution of simultaneous equations, the optimal curve for a given problem. While the derivations to follow are new, the results are equivalent to those of a method due to Hamilton and its modification due to Jacobi.This work was completed by the author during the time of his association with the RAND Corporation Santa Monica, California.     

Necessary and sufficient conditions for a penalty method to be exact

This paper identifies necessary and sufficient conditions for a penalty method to yield an optimal solution or a Lagrange multiplier of a convex programming problem by means of a single unconstrained minimization. The conditions are given in terms of properties of the objective and constraint functions of the problem as well as the penalty function adopted. It is shown among other things that all linear programs with finite optimal value satisfy such conditions when the penalty function is quadratic.     

Convex-concave fractional programming with each variable occurring in a single constraint

The problem considered is that of maximizing the ratio of a concave and a convex function under the assumption that each variable occurs in exactly one component constraint. Such problems occur in the allocation of resources to activities. It is demonstrated that the problem is separable and that componentwise optimization can be applied to determine a solution. A method is given that can be used to evaluate the quality of any feasible solution in terms of an associated upper bound of the optimal value of the objective function: optimal and almost optimal solutions can be recognized. A fast incremental method of generating feasible solutions is described.     

A Lower Bound for the Penalty Parameter in the Exact Minimax Penalty Function Method for Solving Nondifferentiable Extremum Problems

In the paper, we consider the exact minimax penalty function method used for solving a general nondifferentiable extremum problem with both inequality and equality constraints. We analyze the relationship between an optimal solution in the given constrained extremum problem and a minimizer in its associated penalized optimization problem with the exact minimax penalty function under the assumption of convexity of the functions constituting the considered optimization problem (with the exception of those equality constraint functions for which the associated Lagrange multipliers are negative—these functions should be assumed to be concave). The lower bound of the penalty parameter is given such that, for every value of the penalty parameter above the threshold, the equivalence holds between the set of optimal solutions in the given extremum problem and the set of minimizers in its associated penalized optimization problem with the exact minimax penalty function.     

Deriving the Properties of Linear Bilevel Programming via a Penalty Function Approach

For the linear bilevel programming problem, we propose an assumption weaker than existing assumptions, while achieving similar results via a penalty function approach. The results include: equivalence between (i) existence of a solution to the problem, (ii) existence of an exact penalty function approach for solving the problem, and (iii) achievement of the optimal value of the equivalent form of the problem at some vertex of a certain polyhedral convex set. We prove that the assumption is both necessary and sufficient for the linear bilevel programming problem to admit an exact penalty function formulation, provided that the equivalent form of the problem has a feasible solution. A method is given for computing the minimal penalty function parameter value. This method can be executed by solving a set of linear programming problems. Lagrangian duality is also presented.     

Evolutionary Algorithms for Approximate Optimal Control of the Heat Equation with Thermal Sources

In this paper, optimal control problem (OCP) governed by the heat equation with thermal sources is considered. The aim is to find an optimal control which puts the system in a finite time T, into a stationary regime and to minimize a general objective function. To obtain an approximate solution of this problem, a partition of the time-control space is considered and the discrete form of the problem is converted to a quasi assignment problem. Then by using an evolutionary algorithm, an approximate optimal control function is obtained as a piecewise linear function. Numerical examples are given to show the proficiency of the presented algorithm.     

The convex envelope is the solution of a nonlinear obstacle problem

We derive a nonlinear partial differential equation for the convex envelope of a given function. The solution is interpreted as the value function of an optimal stochastic control problem. The equation is solved numerically using a convergent finite difference scheme.

     

Value-Estimation Function Method for Constrained Global Optimization

A novel value-estimation function method for global optimization problems with inequality constraints is proposed in this paper. The value-estimation function formulation is an auxiliary unconstrained optimization problem with a univariate parameter that represents an estimated optimal value of the objective function of the original optimization problem. A solution is optimal to the original problem if and only if it is also optimal to the auxiliary unconstrained optimization with the parameter set at the optimal objective value of the original problem, which turns out to be the unique root of a basic value-estimation function. A logarithmic-exponential value-estimation function formulation is further developed to acquire computational tractability and efficiency. The optimal objective value of the original problem as well as the optimal solution are sought iteratively by applying either a generalized Newton method or a bisection method to the logarithmic-exponential value-estimation function formulation. The convergence properties of the solution algorithms guarantee the identification of an approximate optimal solution of the original problem, up to any predetermined degree of accuracy, within a finite number of iterations.     

Synthesis of a unidirectional systolic array for matrix–vector multiplication

In this paper we present a procedure, based on data dependencies and space–time transformations of index space, to design a unidirectional linear systolic array (ULSA) for computing a matrix–vector product. The obtained array is optimal with respect to the number of processing elements (PEs) for a given problem size. The execution time of the array is the minimal possible for that number of PEs. To achieve this, we first derive an appropriate systolic algorithm for ULSA synthesis. In order to design a ULSA with the optimal number of PEs we then perform an accommodation of the index space to the projection direction vector. The performance of the synthesized array is discussed and compared with the bidirectional linear SA. Finally, we demonstrate how this array can be used to compute the correlation of two given sequences.     

Optimal assignment of NOP due-dates and sequencing in a single machine shop

We consider the problem of optimal assignment of NOP due-dates ton jobs and sequencing them on a single machine to minimize a penalty function depending on the values of assigned constant waiting allowance and maximum job tardiness. It is shown that the earliest due date (EDD) order is an optimal sequence. For finding optimal constant waiting allowance, we reduce the problem to a multiple objective piecewise linear programming with single variable. An efficient algorithm for optimal solution of the problem is given.     

On an optimal shape design problem to control a thermoelastic deformation under a prescribed thermal treatment

A shape optimization problem concerned with thermal deformation of elastic bodies is considered. In this article, measure theory approach in function space is derived, resulting in an effective algorithm for the discretized optimization problem. First the problem is expressed as an optimal control problem governed by variational forms on a fixed domain. Then by using an embedding method, the class of admissible shapes is replaced by a class of positive Borel measures. The optimization problem in measure space is then approximated by a linear programming problem. The optimal measure representing optimal shape is approximated by the solution of this finite-dimensional linear programming problem. Numerical examples are also given.     

A theory for the optimal synthesis of heat-exchanger systems

The problem of the optimal synthesis of heat exchanger systems is treated here with an entirely new approach. It is formulated, using the heat spectrum diagram, as a problem of finding the combination of heat donors and receivers that will minimize a given criterion function. This function is the cost of the heat exchanger system, assumed to be proportional to the total heat-transfer area.The problem is a combinatorial problem for continuous elements. It is solved in general by applying the maximum principle of Pontryagin. The solution for a specific problem is shown to be obtainable by a simple graphical operation.     

Active Constraint Set Invariancy Sensitivity Analysis in Linear Optimization

Active constraint set invariancy sensitivity analysis is concerned with finding the range of parameter variation so that the perturbed problem has still an optimal solution with the same support set that the given optimal solution of the unperturbed problem has. However, in an optimization problem with inequality constraints, active constraint set invariancy sensitivity analysis aims to find the range of parameter variation, where the active constraints in a given optimal solution remains invariant.For the sake of simplicity, we consider the primal problem in standard form and consequently its dual may have an optimal solution with some active constraints. In this paper, the following question is answered: “what is the range of the parameter, where for each parameter value in this range, a dual optimal solution exists with exactly the same set of positive slack variables as for the current dual optimal solution?”. The differences of the results between the linear and convex quadratic optimization problems are highlighted too.     

不等式约束优化问题的低阶精确罚函数的光滑化算法

对不等式约束优化问题提出了一个低阶精确罚函数的光滑化算法. 首先给出了光滑罚问题、非光滑罚问题及原问题的目标函数值之间的误差估计,进而在弱的假
设之下证明了光滑罚问题的全局最优解是原问题的近似全局最优解. 最后给出了一个基于光滑罚函数的求解原问题的算法,证明了算法的收敛性,并给出数值算例说明算法的可行性.     

Reflected BSDEs and robust optimal stopping for dynamic risk measures with jumps

We study the optimal stopping problem for dynamic risk measures represented by Backward Stochastic Differential Equations (BSDEs) with jumps and its relation with reflected BSDEs (RBSDEs). The financial position is given by an RCLL adapted process. We first state some properties of RBSDEs with jumps when the obstacle process is RCLL only. We then prove that the value function of the optimal stopping problem is characterized as the solution of an RBSDE. The existence of optimal stopping times is obtained when the obstacle is left-upper semi-continuous along stopping times. Finally, we investigate robust optimal stopping problems related to the case with model ambiguity and their links with mixed control/optimal stopping game problems. We prove that, under some hypothesis, the value function is equal to the solution of an RBSDE. We then study the existence of saddle points when the obstacle is left-upper semi-continuous along stopping times.     

区间值函数的可微性及其在区间值规划中的应用

利用实值函数的全微分思想,讨论了区间值函数的可微性,建立了区间值函数的$D$-可微性的概念及其一些基本性质. 通过讨论无约束区间规划的最优性条件,给出了一类约束函数为实值函数的约束区间值规划问题取得最优解的必要条件. 同时给出了具有实值函数约束的凸区间值规划问题取得最优解的充分条件.