非线性加工时间单机排序问题

讨论工件加工时间是等待时间的非线性增加函数的单机排序问题,目标函数为极小化完工时间和与极小化最大延误.基于对问题的分析,对于一般非线性函数的情况,给出了工件间的优势关系.对于某些特殊情况,利用工件间的优势关系得到了求解最优排序的多项式算法.推广了文献中的结论.     

具有CON/SLK交货期指派的一类单机排序问题

研究工件的实际加工时间既具有指数学习效应,又依赖所消耗资源的准时制排序问题.在模型中,探讨了共同交货期(CON)和松弛交货期(SLK)两种情形.管理者的目标是确定最优序、最优资源分配方案和最佳工期(共同交货期或松弛交货期)以便极小化工件的总延误、总提前、总工期和资源消耗费用的总和.对于工件的实际加工时间是资源消耗量的线性函数的排序问题,通过将其转化为指派模型,给出了时间复杂性为O(n~3)的算法,从而证明该类排序问题是多项式时间可求解的.针对工件的实际加工时间是资源消耗量的凸函数的排序问题,也给出了多项式算法.     

同时具有学习效应和退化效应的单机排序问题

本文给出了一种同时具有一般化学习效应和退化效应的单机排序模型。在此模型中,工件的实际加工时间既与工件所在位置又与其开工时间有关,且工件在加工之后具有一个配送时间。其中学习效应是工件所在位置的函数,退化效应是工件开工时间的函数。证明了极小化最大完工时间和极小化总完工时间问题是多项式可解的,在满足一定的条件下,极小化加权总完工时间和极小化最大延误问题也是多项式可解的。推广了一些已有文献中的结论。     

具有凸资源约束的单机指数学习效应问题

研究在所有工件的正常加工时间均相同的情况下具有指数学习效应和凸资源约束的单机排序问题.给出了两种模型:在资源消耗总费用有限的情况下,以工件的最大完工时间为目标函数;在工件的最大完工时间有限的情况下,以资源消耗总费用为目标函数.求两种模型下的最优排序和最优资源分配,使得目标函数最小.证明这两个问题都是多项式时间可解的,并给出了相应的算法.     

具有时间与位置相关及维修限制的单机排序问题

考虑时间和位置相关的单机排序问题, 且机器具有退化的维修限制. 工件的实际加工时间是工件加工位置相关的函数, 目标函数为最大完工时间和总完工时间两个函数, 并利用匹配算法给出这两个问题的多项式时间算法. 最后得出工件满足一定条件时最大完工时间满足组平衡规则.     

主指标为最大延迟的主次指标分批排序问题

研究现代排序问题—主指标为最大延迟的主次指标分批排序问题.这里利用动态规划的递推法给出了次指标分别为最大完工时间和误工总数时的多项式时间算法,并给出了次指标为关于工件完工时间的任意正规函数时的拟多项式时间算法.     

两类加工时间是一般函数的单机排序问题

考虑了两类有一般加工时间函数的排序问题. 工件的加工时间分别为基本加工时间与开工时间函数、位置函数的和. 对加工时间依赖开工时间的模型,证明了一定条件下极小化最大完工时间和极小化总完工时间是多项式可解的. 对加工时间依赖开工位置的模型,给出极小化最大完工时间和极小化总完工时间的最优序,同时证明了极小化加权总完工时间的一个最优排序性质并给出一个贪婪算法.     

具有错位限制且工件可退化的单机重新排序问题

重新排序问题是在原始工件已经按照某种最优规则排列时有一批新的工件到达,新工件的安排使得原始工件重新排序而产生错位.考虑了加权序列错位以及加权时间错位限制条件下具有退化工件,目标函数为最小化总完工时间和最小化总延误时间问题.工件的位置错位和时间错位限制条件下具有退化工件,目标函数为最小化总完工时间和最小化最大延迟问题.其中退化效应是指其实际加工时间是开工时间的非减函数,工件的位置错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的加工位置之差,工件的时间错位是指重新排序过程中原始工件在原始最优序列与新到达工件所构成的新序列的完工时间之差.对以上两类问题,当权重系数或者错位限制满足特殊情况时,最优排序是原始工件集和新工件集中的工件按照退化率非减的序列排列,基于动态规划方法给出了以上几个问题的多项式时间算法或者是拟多项式算法.     

基于加工时间之和学习效应下的单机成组排序问题

研究具有加工时间之和学习效应下的一个新型成组排序问题,工件的学习效应是之前工件加工时间之和的函数,组学习效应是成组加工所在的位置的函数. 考虑最大完工时间和总完工时间两个问题,证明了这两个问题都是多项式时间可解的,并提出了相应的多项式时间算法.     

带有固定区间的单机双代理可中断总误工问题

研究带有固定区间的两个代理单机排序问题.第一个代理工件可中断,且工件到达时间与工期满足一致关系,目标函数为最小化总误工.第二个代理工件被安排在固定时间窗口.目标是寻找一个排序,使得满足第二个代理目标可行情况下,第一个代理目标函数值最小.在固定区间等于加工时间的情况下,利用分块原则,提出了一个伪多项式时间动态规划算法,并给出了固定区间大于加工时间情况下的时间复杂度分析.     

工件加工时间增加的排序问题(1‖Cmax)

讨论了工件加工时间随工件开工时间线性增加的排序问题,考虑的目标函数是最大完工时间,证明了加工时间是简单线性增加情况下最大完工时间问题是多项式时间可解的,对于加工时间是一般线性增加情况,研究了最优排序的性质,同时证明了两种特殊情况下最大完工时间问题也是多项式时间可解的。     

The Complexity Analysis of the Inverse Center Location Problem

Given a feasible solution, the inverse optimization problem is to modify some parameters of the original problem as little as possible, and sometimes also with bound restrictions on these adjustments, to make the feasible solution become an optimal solution under the new parameter values. So far it is unknown that for a problem which is solvable in polynomial time, whether its inverse problem is also solvable in polynomial time. In this note we answer this question by considering the inverse center location problem and show that even though the original problem is polynomially solvable, its inverse problem is NP–hard.     

Weighted matching with pair restrictions

The weighted matroid parity problems for the matching matroid and gammoids are among the very few cases for which the weighted matroid parity problem is polynomial time solvable. In this work we extend these problems to a general revenue function for each pair, and show that the resulting problem is still solvable in polynomial time via a standard weighted matching algorithm. We show that in many other directions, extending our results further is impossible (unless P = NP). One consequence of the new polynomial time algorithm is that it demonstrates, for the first time, that a prize-collecting assignment problem with “pair restriction” is solved in polynomial time. The prize collecting assignment problem is a relaxation of the prize-collecting traveling salesman problem which requires, for any prescribed pair of nodes, either both nodes of the pair are matched or none of them are. It is shown that the prize collecting assignment problem is equivalent to the prize collecting cycle cover problem which is hence solvable in polynomial time as well.     

Algorithm for verifying the equivalence of linear unary recursive programs on ordered semigroup scales

A new method for solving the problem of equivalence of linear unary recursive programs is proposed. The main idea behind this method is to reduce the equivalence problem to known problems on graphs and to problems in group theory. A class of program semantics is singled out for which the problem of the equivalence of the programs in question is solvable in polynomial time by the proposed method.     

The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes

The exact weighted independent set (EWIS) problem consists in determining whether a given vertex-weighted graph contains an independent set of given weight. This problem is a generalization of two well-known problems, the NP-complete subset sum problem and the strongly NP-hard maximum weight independent set (MWIS) problem. Since the MWIS problem is polynomially solvable for some special graph classes, it is interesting to determine the complexity of this more general EWIS problem for such graph classes.We focus on the class of perfect graphs, which is one of the most general graph classes where the MWIS problem can be solved in polynomial time. It turns out that for certain subclasses of perfect graphs, the EWIS problem is solvable in pseudo-polynomial time, while on some others it remains strongly NP-complete. In particular, we show that the EWIS problem is strongly NP-complete for bipartite graphs of maximum degree three, but solvable in pseudo-polynomial time for cographs, interval graphs and chordal graphs, as well as for some other related graph classes.     

Single machine scheduling subject to deadlines and resource dependent processing times

The problem of scheduling n jobs on a single machine is studied. Each job has a deadline and a processing time which is a linear decreasing function of the amount of a common resource allocated to the job. The objective is to find simultaneously a sequence of the jobs and a resource allocation so as the deadlines are satisfied and the total weighted resource consumption is minimized. The problem is shown to be solvable in O(n log n) time if the resource is continuously divisible. If the resource is discrete, then the problem is proved to be binary NP-hard. Some special cases are solvable in O(n log n) time. A fully polynomial approximation scheme is presented for the general problem with discrete resource.     

On the initial boundary value problem for a nonlinear nonhomogeneous equation of Sobolev type

The initial boundary value problem for a nonlinear nonhomogeneous equation of Sobolev type used for modeling nonstationary processes in semiconductors is examined. It is proved that this problem is uniquely solvable at least locally in time. Sufficient conditions for the problem to be solvable globally in time are found, as well as sufficient conditions for the local (but not global) solvability. In the case of only local solvability, upper and lower estimates for the time when a solution exists are determined in the form of either explicit or quadrature formulas.     

On degree sequence optimization

We consider the problem of finding a subgraph of a given graph maximizing a given function evaluated at its degree sequence. While it is intractable already for convex functions, we show it is polynomial time solvable for convex multi-criteria objectives. We also consider a colored extension of the problem with separable objectives, which includes the notorious exact matching problem as a special case, and show that it is polynomial time solvable on graphs of bounded tree-depth for any vertex functions.     

An asymmetric analog of van der Veen conditions and the traveling salesman problem (II)

J.A.A. van der Veen [A new class of pyramidally solvable symmetric traveling salesman problems, SIAM J. Discrete Math. 7 (1994) 585–592] proved that for the traveling salesman problem (TSP) which satisfies some symmetric conditions (called van der Veen conditions), a shortest pyramidal tour is optimal, that is, an optimal tour can be computed in polynomial time. In this paper, we prove that a class satisfying an asymmetric analog of van der Veen conditions is polynomially solvable. An optimal tour of the instance in this class forms a tour which is an extension of pyramidal ones. Moreover, this class properly includes some known polynomially solvable classes.     

工时依赖于开工时间的单台机排序问题

此文考察工时依赖于开工时间的排序问题．文章证明：(1)即使准奋时间完全相同，判断工时与开工时间相关的单台机排序问题是否有可行解也是NP完全的．(2)即使只存在两个不同的截止期，判断工时与开工时间相关的单台机排序问题是否有可行解仍然是NP完全的．(3)当所有工件有相同截止期时，问题是否有可行解可在多项式时间内判定．