总延误问题顺时安排法的性能比

给定一组工件的加工时间与工期，要求确定这些工件在一台机器上的加．工排列，使相应的总延误达到最小，这就是总延误问题．该问题在近年已被证明是NP困难的．由Wilkermn和Irwin（1971），林勋（1983）等所研究的顺时安排法能得到相邻交换意义下的局部解．在本文中，我们进一步证明该算法能得到前移邻域意义下的局部解，并确定了该算法的性能比．     

带交互作用测度值分枝过程的绝对连续性

本文研究Meleard-Roelly（1992，1993）和Metivier（1987）构造的带交互作用的测度值分枝过程的状态性质．我们证明在自然假设下该过程关于Lebesgue测度是绝对连续的，其密度有连续修正且满足一个随机偏微分方程．     

最优化中的几个问题解的等价性

考虑如下非线性规划问题：众所周知，问题（NP）的解法主要有三类：1．直接处理约束，2．将约束最优化问题化为 无约束最优化问题来处理，3．将（NP）化为简单的约束最优化问题如线性规划或二次规划等来处理，而将约束最优化问题化为无约束最优化问题的主要手段是利用如下的Lagrange函数：L（X，X，X）一八X）＋（X，g（X》十（X，h（X》（1．I）定义1．1称点卜”，V”撤足互补性条件，如果对”（X）一ojE【I：c］（亚．2）根据Lagrange函数（1．1）定义如下问题：（SPP）：求点k”，u”，v」6H””，m二。；＋c，使b“，u“，v」…     

一类拟线性抛物型方程间断初边值问题

本文我们将讨论拟线性抛物型方程具间断数据的初边值问题（１）－（３）．在某些条件下，我们将证明问题的有界解的存在、唯一性及解在间断点处的性态．     

WDM网络中的排序与波长分配问题的一个多项式时间近似方案

本文考虑基于波分复用技术 (WDM)的光学网络中的排序与波长分配问题 .在波长数目固定的情况下 ,我们证明此问题是NP 困难问题 ,并且给出一个多项式时间近似方案 .若波长数目不固定 ,我们证明此问题不存在多项式时间近似方案     

带参在线箱覆盖问题

我们考虑在线箱覆盖问题,其中所有被装元素的尺寸不超过1／k（k是正整数）．我们给出了该问题的紧上界并证明简单算法NextFit即是最好的．这个结果推广了Csirik与Totik1988年的工作．最后,我们还给出了二维情形的一个非平凡的上界．     

线性同胚于星象函数的一族解析函数

本文定义了线性同胚于星象函数的－族解析函数Ａ（，α）．我们导出Ａ（α）中函数的积分表达式：借助算子理论研究Ａ（，α）族的包含关系并确定它的闭凸包、闭凸包的极值点和它的支撑点；利用一个阶微分从属证明关于实部的二个不等式．最后，我们还证明Ａ（，α）中函数的偏差定理．     

设置增量证明不等式

等与不等是对立与统一的一对矛盾，在某种意义下又常常是可以相互转化的．例如在证明不等式的过程中，我们可用设置增量的方法将不等关系转化为相等关系，以达到证明不等式的目的．例1已知a＞2，b＞2．求证：ab＞a＋b．（根据1993年湖北省初中数学竞赛题改编）证明∵a＞2，b＞2可设a＝2＋m，b＝2＋n，m＞0，n＞0．∵ab－（a＋b）＝（2＋m）（2＋n）－（2＋m＋2＋n）＝mn＋m＋n＞0ab＞a＋b．例2设a＞2，给定数列{Xn}，其中证明（用数学归纳法）当n＝1时，x1=a＞2成立．若n＝k时，有Xk＞2，不妨设Xk＝2＋m，m＞0．即，因此对一切自然数n都有…     

一阶逻辑归约与计算复杂性

在计算科学中,NP完全问题在区分可计算问题的复杂度类发挥着重大的作用,不仅是因为任意NP问题都可多项式时间归约到此类问题,而且若存在一个NP完全问题在确定图灵机多项式时间内可解,那么,所有的NP问题都可在多项式时间内解决.现在广泛认为NP完全问题不存在多项式时间算法,尽管尚未有效地证明,但识别一个问题是否为NP完全问题已经显得尤为重要.从描述复杂性角度阐述计算复杂性与逻辑之间的关联,通过具体实例:集合覆盖和控制集问题,讲述如何应用一阶投射方法证明一个NP问题的完全性.这种通过逻辑归约的方法被证明是十分有用的:只需要很少的公式而不再是冗长的证明.而逻辑归约的作用不仅在于此,在P类问题中应用逻辑归约时,发现计数最小不动点逻辑LFP+C,计数膨胀不动点逻辑IFP+C和C_(∞ω)~ω对P类问题的表达能力并不充分.     

O'下纯正多项式极小度的存在性

引言Homer 在中证明了在 P=NP 条件下可以证明 O′下纯正多项式极小度的存在性,他还证明了若干种 O″下的集不具有纯正多项式极小度.如果可以证明一切 O″下的集都不具有纯正极小度,那么可以证明 P≠NP。因此 Homer 的工作给出了一个解决“P=?NP”问题的一个可能途径.本文目的是在 P=NP 条件下证明在 O′下存在纯正多项式极小度.这样只须证明一切O′下的集都不具有纯正多项式极小度,则有 P≠NP.从而可以使证明 P≠NP 的这种途径     

A note on the paper “Resource-constrained project scheduling: Notation,classification, models and methods” by Brucker et al.

The great variety of project scheduling problems studied in the ever growing literature motivated the recent development of classification schemes. In a recent paper (European Journal of Operational Research 112 (1999) 3–41), Brucker et al. make the claim that, so far, no classification scheme exists which is compatible with what is commonly accepted in machine scheduling and introduce a new classification. In this note, we critically review major shortcomings of the suggested scheme which place heavy limitations on its potential use.     

Depth-first heuristic search for the job shop scheduling problem

We evaluate two variants of depth-first search algorithms and consider the classic job shop scheduling problem as a test bed. The first one is the well-known branch-and-bound algorithm proposed by P. Brucker et al. which uses a single chronological backtracking strategy. The second is a variant that uses partially informed depth-first search strategy instead. Both algorithms use the same heuristic estimation; in the first case, it is only used for pruning states that cannot improve the incumbent solution, whereas in the second it is also used to sort the successors of an expanded state. We also propose and analyze a new heuristic estimation which is more informed and more time consuming than that used by Brucker’s algorithm. We conducted an experimental study over well-known instances showing that the proposed partially informed depth-first search algorithm outperforms the original Brucker’s algorithm.     

Minimizing the weighted number of late jobs in UET open shops

We consider a two-machine open shop problem where the jobs have release dates and due dates, and where all single operations have unit processing times. The goal is to minimize the weighted number of late jobs. We derive a polynomial time algorithm for this problem, thereby answering an open question posed in a recent paper by Brucker et al.This research was supported by the Christian Doppler Laboratorium für Diskrete Optimierung.     

Minimizing the total completion time in a unit-time open shop with release times

We consider the problem of minimizing the total completion time in a unit-time open shop with release times where the number of machines is constant. Brucker and Krämer (1994) proved that this problem is solvable in polynomial time. However, the time complexity of the algorithm presented there is a polynom of a very high degree and, thus, the algorithm is not practicable even for a small number of machines. We give an O(n²) algorithm for the considered problem which is based on dynamic programming. The result is applied to solve a previously open problem with a special resource constraint raised by De Werra et al. (1991).     

An efficient algorithm for a job shop problem

We study the problem of minimizing makespan in a two-machine job shop with unit processing time operations. An efficient algorithm with respect to a succinct encoding of the problem instances is proposed. The algorithm is an improvement of earlier algorithms proposed for the problem by Brucker [1,2], Hefetz and Adiri [7], and Timkovskiy [15]. The idea behind the algorithm has the potential of extension to job shops with parallel machines.This research is supported in part by NSERC Grants A4619, OGP0105675, OGP0104900, General Motors of Canada, and the Manufacturing Research Corporation of Ontario.     

An extended algorithm for optimal product positioning

Optimal product positioning in an attribute space has been formulated according to the axiom of choice as a mixed integer nonlinear programming problem. To solve it, Albers and Brockhoff have designed the special purpose algorithm PROPOSAS. It works under simplified assumptions: Euclidean metric, equally weighted dimensions of the attribute space and equal sales per customer. The following article shows that the basic ideas of PROPOSAS are flexible enough to be expanded to cover a weighted Minkowski-metric as well as different revenues from the customers. Furthermore, the calculation of a new upper bound is described which reduces CPU-time considerably.     

Empirical likelihood method for intermediate quantiles

Intermediate quantiles play an important role in the statistics of extremes with particular applications in risk management. For interval estimation of quantiles, Chen and Hall (1993) proposed the so-called smoothed empirical likelihood method. In this paper, we apply the method in Chen and Hall (1993) to construct confidence intervals for an intermediate quantile by deriving the corresponding Wilks Theorem.     

Minimizing total completion time for UET tasks with release time and outtree precedence constraints

Brucker et al. (Math Methods Oper Res 56: 407–412, 2003) have given an O(n ²)-time algorithm for the problems , outtree and , outtree . In this note, we show that their algorithm admits an O(n log n)-time implementation.     

A demand adjustment process

The aspiration approach to cooperative games, which has been studied by a number of authors, including Cross, Turbay, Albers, Selten and Bennett, presumes that players in a game bargain over their reservation prices, or aspirations. A number of aspiration-based solution concepts have been put forth, and aspiration solutions have been connected to non-cooperative bargaining models. Missing in this approach has been theory of how aspirations themselves arise. The present paper is an attempt to fill this gap. It describes a very general demand adjustment process, using the framework of set-valued dynamical systems developed by Maschler and Peleg. This demand adjustment process always converges; sufficient conditions are given in order that it converge to an aspiration, and that it converge in a finite number of steps.     

The regularization method for an obstacle problem

Summary. We give a relatively complete analysis for the regularization method, which is usually used in solving non-differentiable minimization problems. The model problem considered in the paper is an obstacle problem. In addition to the usual convergence result and a-priori error estimates, we provide a-posteriori error estimates which are highly desired for practical implementation of the regularization method. Received March 22, 1993 / Revised version received October 11, 1993