Heuristic Solution Methods for the Multilevel Generalized Assignment Problem

The multilevel generalized assignment problem is a problem of assigning agents to tasks where the agents can perform tasks at more than one efficiency level. A profit is associated with each assignment and the objective of the problem is profit maximization. Two heuristic solution methods are presented for the problem. The heuristics are developed from solution methods for the generalized assignment problem. One method uses a regret minimization approach whilst the other method uses a repair approach on a relaxation of the problem. The heuristics are able to solve moderately large instances of the problem rapidly and effectively. Procedures for deriving an upper bound on the solution of the problem are also described. On larger and harder instances of the problem one heuristic is particularly effective.     

Complexities and algorithms for synchronized scheduling of parallel machine assembly and air transportation in consumer electronics supply chain

In this paper, we study the problem of synchronized scheduling of assembly and air transportation to achieve accurate delivery with minimized cost in consumer electronics supply chain. This problem was motivated by a major PC manufacturer in consumer electronics industry. The overall problem is decomposed into two sub-problems, which consist of an air transportation allocation problem and an assembly scheduling problem. The air transportation allocation problem is formulated as an integer linear programming problem with the objective of minimizing transportation cost and delivery earliness tardiness penalties. The assembly scheduling problem seeks to determine a schedule ensuring that the orders are completed on time and catch the flights such that the waiting penalties between assembly and transportation is minimized. The problem is formulated as a parallel machine scheduling problem with earliness penalties. The computational complexities of the two sub-problems are investigated. The air transportation allocation problem with split delivery is shown to be solvable. The parallel machine assembly scheduling problem is shown to be NP-complete. Simulated annealing based heuristic algorithms are presented to solve the parallel machine problem.     

On optimal shape design of systems governed by mixed Dirichlet-Signorini boundary value problems

A problem for finding optimal shape for systems governed by the mixed unilateral boundary value problem of Dirichlet-Signorini-type is considered. Conditions for the solvability of the problem are stated when a variational inequality formulation and when a penalty method is used for solving the state problem in question. The asymptotic relation of design problems based on these two formulations is presented. The optimal shape design problem is discretized by means of finite element method. The convergence results for the approximation are proved. The discretized versions are then formulated as a non-linear programming problem. Results of practical computations of the problem in question are reported.     

Scheduling a single machine to minimize earliness penalties subject to the SLK due-date determination method

This paper considers a single machine scheduling problem. There are n jobs to be processed on a single machine. The problem is to minimize total earliness penalties subject to no tardy jobs. The problem is NP-complete if the due-dates are arbitrary. We study the problem when the due-dates are determined by the equal slack (SLK) method. Two special cases of the problem are solved in polynomial time. The first one is the problem with equally weighted monotonous penalty objective function. The second one is the problem with weighted linear penalty objective function.     

Uncertain solid transportation problems

The solid transportation problem arises when bounds are given on three item properties. Usually, these properties are source, destination and type of product or mode of transport, and often are given in a uncertain way. This paper deals with two of the ways in which uncertainty can appear in the problem: Interval solid transportation problem and fuzzy solid transportation problem. The first arises when data problem are expressed as intervals instead of point values, and the second when the nature of the information is vague. Both models are treated in the case in which the uncertainty affects only the constraint set. For interval case, an auxiliary problem is obtained in order to find a solution. This auxiliary problem is a standard solid transportation problem which can be solved with the efficient methods existing. For fuzzy case, a parametric approach which makes it possible to find a fuzzy solution to the former problem is used.     

Unconstrained Methods for Generalized Complementarity Problems

1.IntroductionThecomplementarityproblem,aspecialcaseofvariationalinequalityproblem,hasmanyapplicationsindifferentfieldssuchasmathematicalprogramming,gametheory,economics.Generally,thestandardcomplementarityproblemhasthefollowingform:y=F(x),x20,y20,(y,x)=0,(1.1)where(.,.)denotestheinnerproducts.WhenF(x)isanaffinefunctionofx,itreducestothelinearcomplementarityproblemwhichisdenotedbyLCP.Otherwisewecallitthenonlinearco7nplementaritypro6lemorsimplyNCP.Thecomplementarityproblemhajsattractedmanyr…     

The reformulation of two mixed integer programming problems

Two practical problems are described, each of which can be formulated in more than one way as a mixed integer programming problem. The computational experience with two formulations of each problem is given. It is pointed out how in each case a reformulation results in the associated linear programming problem being more constrained. As a result the reformulated mixed integer problem is easier to solve. The problems are a multi-period blending problem and a mining investment problem.     

Mathematical modeling and study of the process of solidification in metal casting

The process of melting and solidification in metal casting is considered. The process is modeled by a three-dimensional two-phase initial-boundary value problem of the Stefan type. The mathematical formulation of the problem and its finite-difference approximation are given. A numerical algorithm is presented for solving the direct problem. The results are described and analyzed in detail. Primary attention is given to the evolution of the solidification front and to how it is affected by the parameters of the problem. Some of the results are illustrated by plots.     

A Note on the Stability of the Integral-Differential Equation of the Hyperbolic Type in a Hilbert Space

In this paper, the initial-value problem for integral-differential equation of the hyperbolic type in a Hilbert space H is considered. The unique solvability of this problem is established. The stability estimates for the solution of this problem are obtained. The difference scheme approximately solving this problem is presented. The stability estimates for the solution of this difference scheme are obtained. In applications, the stability estimates for the solutions of the nonlocal boundary problem for one-dimensional integral-differential equation of the hyperbolic type with two dependent limits and of the local boundary problem for multidimensional integral-differential equation of the hyperbolic type with two dependent limits are obtained. The difference schemes for solving these two problems are presented. The stability estimates for the solutions of these difference schemes are obtained.     

Optimization of rod antennas of mobile phones

Two types of rod antennas of mobile phones are optimized so that the radiated energy absorbed by the head or body of the user is reduced and the radiation intensity to other areas especially to the receiver is increased. The mathematical modelling of this problem leads to an infinite dimensional bicriterial optimization problem. It is shown that this optimization problem and a discretized version of this problem are solvable. The relationship between the infinite and finite dimensional optimization problem is investigated. Numerical results are presented for mobile phones working with the GSM standards 900 and 1800.     

Solving the discrete-continuous project scheduling problem via its discretization

In this paper a discrete-continuous project scheduling problem is considered. In this problem activities simultaneously require discrete and continuous resources. The processing rate of each activity depends on the amount of the continuous resource allotted to this activity at a time. All the resources are renewable ones. The activities are nonpreemtable and the objective is to minimize the makespan. Discretization of this problem leading to a classical (i.e. discrete) project scheduling problem in the multi-mode version is presented. A simulated annealing (SA) approach to solving this problem is described and tested computationally in two versions: with and without finding an optimal continuous resource allocation for the final schedule. In the former case a nonlinear solver is used for solving a corresponding convex programming problem. The results are compared with the results obtained using SA for the discrete-continuous project scheduling problem where the nonlinear solver is used for exact solving the continuous part in each iteration. The results of a computational experiment are analyzed and some conclusions are included.     

偶图的补图的侧廓问题和填充问题的NP-完全性

本文研究偶补图的侧廓问题和填充问题的计算复杂性，证明了：即使对直径不超过2的偶补图，侧廓问题和填充问题也是NP－完全的．     

Continuous quadratic programming formulations of optimization problems on graphs

Four NP-hard optimization problems on graphs are studied: The vertex separator problem, the edge separator problem, the maximum clique problem, and the maximum independent set problem. We show that the vertex separator problem is equivalent to a continuous bilinear quadratic program. This continuous formulation is compared to known continuous quadratic programming formulations for the edge separator problem, the maximum clique problem, and the maximum independent set problem. All of these formulations, when expressed as maximization problems, are shown to follow from the convexity properties of the objective function along the edges of the feasible set. An algorithm is given which exploits the continuous formulation of the vertex separator problem to quickly compute approximate separators. Computational results are given.     

INVERSE EIGENVALUE PROBLEM OF HERMITIAN GENERALIZED ANTI-HAMILTONIAN MATRICES

§1　IntroductionWe considerthe following inverse eigenvalue problem offinding an n-by-n matrix A∈S such thatAxi =λixi,i =1,2 ,...,m,where S is a given set of n-by-n matrices,x1 ,...,xm(m≤n) are given n-vectors andλ1 ,...,λmare given constants.Let X=(x1 ,...,xm) ,Λ=(λ1 ,λ2 ,...,λm) ,then the above inverse eigenvalue problemcan be written as followsProblem Given X∈Cn×m,Λ=(λ1 ,...,λm) ,find A∈S such thatAX =XΛ,where S is a given matrix set.We also discuss the so-called opti…     

Solution of Finite-Dimensional Variational Inequalities Using Smooth Optimization with Simple Bounds

The variational inequality problem is reduced to an optimization problem with a differentiable objective function and simple bounds. Theoretical results are proved, relating stationary points of the minimization problem to solutions of the variational inequality problem. Perturbations of the original problem are studied and an algorithm that uses the smooth minimization approach for solving monotone problems is defined.     

Arc routing problems with time-dependent service costs

This paper studies an arc routing problem with capacity constraints and time-dependent service costs. This problem is motivated by winter gritting applications where the “timing” of each intervention is crucial. The exact problem-solving approach reported here first transforms the arc routing problem into an equivalent node routing problem. Then, a column generation scheme is used to solve the latter. The master problem is a classical set covering problem, while the subproblems are time-dependent shortest path problems with resource constraints. These subproblems are solved using an extension of a previously developed algorithm. Computational results are reported on problems derived from a set of classical instances of the vehicle routing problem with time windows.     

三种新变形的全一问题

该文研究三种新变形的全一问题及最小全一问题. 原始的全一问题可被形象的称为顶点点亮顶点问题, 而这三类新问题则分别被称为顶点点亮边问题,边点亮顶点问题,边点亮边问题. 顶点点亮顶点问题已经得到了广泛的研究. 比如,解的存在性问题和求解的有效算法已经被解决,一般图上的最小顶点点亮顶点问题已经被证明是NP- 完备的,树、单圈图和双圈图上的最小顶点点亮顶点问题的线性时间最优算法也已被给出等. 该文对于顶点点亮边问题,证明一个图有解当且仅当它是二部图,因此只可能有两组解和最优解. 对于边点亮顶点问题,证明一个图有解当且仅当它包含偶数个顶点,并通过将其最优问题多项式变换成最小权的完美匹配问题,得出一般图上的最小边点亮顶点问题可在多项式时间内求解. 边点亮边问题可归约成线图上的顶点点亮顶点问题.     

Linear optimal control problem for discrete 2-D systems with constraints

Optimal control problem for linear two-dimensional (2-D) discrete systems with mixed constraints is investigated. The problem under consideration is reduced to a linear programming problem in appropriate Hubert space. The main duality relations for this problem is derived such that the optimality conditions for the control problem are specified by using methods of the linear operator theory. Optimality conditions are expressed in terms of solutions for conjugate system.     

Boundary-value problems for an elliptic equation with complex coefficients and a certain moment problem

Elliptic systems of two second-order equations, which can be written as a single equation with complex coefficients and a homogeneous operator, are studied. The necessary and sufficient conditions for the connection of traces of a solution are obtained for an arbitrary bounded domain with a smooth boundary. These conditions are formulated in the form of a certain moment problem on the boundary of a domain; they are applied to the study of boundary-value problems. In particular, it is shown that the Dirichlet problem and the Neumann problem are solvable only together. In the case where the domain is a disk, the indicated moment problem is solved together with the Dirichlet problem and the Neumann problem. The third boundary-value problem in a disk is also investigated.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 45, No. 11, pp. 1476–1483, November, 1993.     

一种新的向量互补问题

本文在实局部凸空间中引入了一种新的向量互补问题,这一向量互补问题不仅包含了由Ｙｕ和Ｙａｏ提出的广义向量互补问题由Ｃｈｅｎ和Ｙａｎｇ定义的弱向量互补问题,而且还包含了Ｉｓａｃ意义下的隐互补问题。本文还讨论了新的向量互补问题,向量变分不等式,向量单向极小化问题和最小元问题之间的关系,给出了这一向量互补问题解的存在定理。