加工时间可控和恶化的单机最大完工时间排序

本文研究加工时间可控并随开工时间简单线性增长的单机最大完工时间排序问题.该问题将加工时间可控排序和加工时间恶化排序两类研究连接到一起.通过比较技术证明了该问题存在满足以下性质的最优解:每个工件的加工时间或者完全压缩,或者完全不压缩;加工时间完全压缩的工件的顺序由一个工件参数和控制变量的函数的递增序给出,完全不压缩的工件在完全压缩的工件之后以任意序加工.通过将问题等价转换为0-1非线性整数规划问题,给出了单机排序问题的贪婪算法.     

加工时间可控和简单线性增长的平行机排序

本文研究加工时间可控并随开工时间简单线性增长的平行机排序问题.证明了该问题为NP-难问题,该问题存在满足以下性质的最优排序:每个工件的加工时间要么完全压缩,要么完全不压缩;每台机器的工件排序由一个工件参数和控制变量的函数的递增序给出.通过将问题等价转换为0-1非线性整数规划问题,给出了平行机排序问题的贪婪算法.     

单机主次指标排序问题1|(rj, dj) agreeable, pj = p, pmtn|∑Uj|Tmax

本文研究了单机主次指标排序问题1|rj,pmtn|∑Uj|Tmax．在同工期且准备时间和工期具有一致性的情形下，给出了该问题的允许中断抢先的多项式时间算法．     

离散加工时间的可控排序问题

本文主要研究了离散加工时间的可控排序问题,目标函数是总压缩费用约束下极小化最大完工时间,对单机工件有不同到达时间以及同型机工件到达时间都相同这两个问题,我们设计了伪多项式时间的动态规划算法,并给出了相应的FPTAS算法．     

基于拟凸损失的核正则化成对学习算法的收敛速度

核正则化排序算法是目前机器学习理论领域讨论的热点问题,而成对学习算法是排序算法的推广.文章给出一种基于拟凸损失的核正则化成对学习算法,利用拟凸分析理论对该算法进行误差分析,给出算法的收敛速度.分析结果表明,算法的样本误差与损失函数中的参数选择有关.数值实验结果显示,与基于最小二乘损失的排序算法相比较,该算法有更稳健的学习性能.     

机器具有优势关系下的工件加工时间可控的流水作业排序问题

本文主要研究机器具有优势关系下的工件加工时间可控的流水作业排序问题.我们主要对以下两种情形进行了讨论:工件加工时间为线性恶化和线性学习.对于每一种加工模型,我们分别研究了几类不同的优势机器,并且对每种情况均给出了多项式时间算法.     

具有机器故障的单机随机JIT排序问题

对中断－继续和中断－重复两种模型研究具有机器故障的单机随机JIT排序问题, 目标函数是期望完工时间 与工期方差和. 对中断－继续模型证明SSDE问题的最优排序具有关于期望加工时间的V-形性质, 并给出了一个拟多项式 的动态规划算法. 同时对SSDE问题和ESSD问题 进行了比较, 证明了SSDE问题的最优解是一个非常好的ESSD问题的近似最优解. 在一定的条件下, SSDE问题 的最优解就是ESSD问题的最优解. 对中断－重复模型, 由于完工时间的方差无法求出, JIT排序问题至今没得到解决, 故从实际 应用角度用SSDE问题替代ESSD问题, 证明了SSDE问题最优解具有关于期望占用机器时间的V-形性质, 并给出了 一个拟多项式的动态规划算法, 提出了一个研究JIT问题的中断－重复模型的新思路.     

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

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

所有初始数据皆近似的第一类算子方程的带有闭线性算子的正则化

本文利用带有闭线性算子的正则化，来解第一类算子方程．当所有初始数据皆近似已知时，按照广义Ａｒｃａｎｇｅｌｉ准则选取正则化参数，并给出了正则解的收敛性和收敛渐近阶估计．     

机器具有准备时间的双目标平行机排序问题

本文讨论机器具有准备时间的双目标平行机排序问题，目标函数为完工时间和最优条件下极小化最大完工时间．通过对SPT排序的性质的分析，给出了最优排序的下界．在此基础上证明了SPT排序的误差界为3／2，并且是紧界．     

A new bounding mechanism for the CNC machine scheduling problems with controllable processing times

In this study, we determine the upper and lower bounds for the processing time of each job under controllable machining conditions. The proposed bounding scheme is used to find a set of discrete efficient points on the efficient frontier for a bi-criteria scheduling problem on a single CNC machine. We have two objectives; minimizing the manufacturing cost (comprised of machining and tooling costs) and minimizing makespan. The technological restrictions of the CNC machine along with the job specific parameters affect the machining conditions; such as cutting speed and feed rate, which in turn specify the processing times and tool lives. Since it is well known that scheduling problems are extremely sensitive to processing time data, system resources can be utilized much more efficiently by selecting processing times appropriately.     

Scheduling with controllable release dates and processing times: Total completion time minimization

The single machine scheduling problem with two types of controllable parameters, job processing times and release dates, is studied. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amounts. The objective is to minimize the sum of the total completion time of the jobs and the total compression cost. For the problem with equal release date compression costs we construct a reduction to the assignment problem. We demonstrate that if in addition the jobs have equal processing time compression costs, then it can be solved in O(n²) time. The solution algorithm can be considered as a generalization of the algorithm that minimizes the makespan and total compression cost. The generalized version of the algorithm is also applicable to the problem with parallel machines and to a range of due-date scheduling problems with controllable processing times.     

具有学习效应和加工时间可控的平行机排序问题

本文研究了一类不相关平行机的排序问题,在该问题中工件的加工时间既具有学习效应,又资源可控,也就是说在该问题模型中,工件的实际加工时间为其正常的加工时间、加工过程中工件所处位置以及加工时间可控这些变量的函数。该研究的目的是为使得总机器负载和总的控制费用的加权和最小以及总的完工时间和总的控制费用的加权和最小。文章通过对问题的相关性质的分析和证明找到了一个解决问题的最优化算法,并且也证明了在处理机的数量给定的条件下,该问题的时间复杂性为O(n^m+2),最后也给出了相应的数值例子来阐述该问题。     

A survey of scheduling with controllable processing times

In classical deterministic scheduling problems, the job processing times are assumed to be constant parameters. In many practical cases, however, processing times are controllable by allocating a resource (that may be continuous or discrete) to the job operations. In such cases, each processing time is a decision variable to be determined by the scheduler, who can take advantage of this flexibility to improve system performance. Since scheduling problems with controllable processing times are very interesting both from the practical and theoretical point of view, they have received a lot of attention from researchers over the last 25 years. This paper aims to give a unified framework for scheduling with controllable processing times by providing an up-to-date survey of the results in the field.     

Scheduling with controllable release dates and processing times: Makespan minimization

The paper deals with the single-machine scheduling problem in which job processing times as well as release dates are controllable parameters and they may vary within given intervals. While all release dates have the same boundary values, the processing time intervals are arbitrary. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amount. The objective is to minimize the makespan together with the total compression cost. We construct a reduction to the assignment problem for the case of equal release date compression costs and develop an O(n²) algorithm for the case of equal release date compression costs and equal processing time compression costs. For the bicriteria version of the latter problem with agreeable processing times, we suggest an O(n²) algorithm that constructs the breakpoints of the efficient frontier.     

Optimal allocation and processing time decisions on non-identical parallel CNC machines: ϵ-constraint approach

When the processing times of jobs are controllable, selected processing times affect both the manufacturing cost and the scheduling performance. A well known example for such a case that this paper specifically deals with is the turning operation on a CNC machine. Manufacturing cost of a turning operation is a nonlinear convex function of its processing time. In this paper, we deal with making optimal machine-job assignments and processing time decisions so as to minimize total manufacturing cost while the makespan being upper bounded by a known value, denoted as ?-constraint approach for a bicriteria problem. We then give optimality properties for the resulting single criterion problem. We provide alternative methods to compute cost lower bounds for partial schedules, which are used in developing an exact (branch and bound) algorithm. For the cases where the exact algorithm is not efficient in terms of computation time, we present a recovering beam search algorithm equipped with an improvement search procedure. In order to find improving search directions, the improvement search algorithm uses the proposed cost bounding properties. Computational results show that our lower bounding methods in branch and bound algorithm achieve a significant reduction in the search tree size that we need to traverse. Also, our recovering beam search and improvement search heuristics achieve solutions within 1% of the optimum on the average while they spent much less computational effort than the exact algorithm.     

延误工件个数与最大加工时间压缩比例之和的可控排序

研究工件加工时间可控的排序问题，讨论的目标函数是延误工件个数与最大加工时间压缩比例之和，证明这一问题是多项式时间可解的。     

Minimizing the sum of job completion times on capacitated two-parallel machines

This paper considers a scheduling problem with two identical parallel machines. One has unlimited capacity; the other can only run for a fixed time. A given set of jobs must be scheduled on the two machines with the goal of minimizing the sum of their completion times. The paper proposes an optimal branch and bound algorithm which employs three powerful elements, including an algorithm for computing the upper bound, a lower bound algorithm, and a fathoming condition. The branch and bound algorithm was tested on problems of various sizes and parameters. The results show that the algorithm is quite efficient to solve all the test problems. In particular, the total computation time for the hardest problem is less than 0.1 second for a set of 100 problem instances. An important finding of the tests is that the upper bound algorithm can actually find optimal solutions to a quite large number of problems.     

Computational experience with a group theoretic integer programming algorithm

This paper gives specific computational details and experience with a group theoretic integer programming algorithm. Included among the subroutines are a matrix reduction scheme for obtaining group representations, network algorithms for solving group optimization problems, and a branch and bound search for finding optimal integer programming solutions. The innovative subroutines are shown to be efficient to compute and effective in finding good integer programming solutions and providing strong lower bounds for the branch and bound search.This research was supported in part by the U.S. Army Research Office (Durham) under contract no. DAHC04-70-C-0058. This paper is not an official National Bureau of Economic Research publication.     

Multiple-Project Scheduling with Controllable Project Duration and Hard Resource Constraint: Some Solvable Cases

In many large-scale project scheduling problems, multiple projects are either taking place at the same time or scheduled into a tight sequence in order to efficiently share a common resource. One example of this is the computing resource allocation at an Application Service Provider (ASP) which provides data processing services for multiple paying customers. Typical services provided by ASPs are data mining, payroll processing, internet-based storage backup services and Customer Relation Management (CRM) services. The processing mode of an ASP can be either batch or concurrent, depending on the type service rendered. For example, for CPU intensive or long processing time required services, it would be more economical to processes one customer request at a time in order to minimize the context switching overhead. While the data transaction processes within a service request are subject to certain precedence relationships, the requests from different customers to an ASP are independent of each other, and the total time required to process a service request depends on the computing resource allocated to that request. The related issue of achieving an optimal use of resources at ASPs leads to problem of project scheduling with controllable project duration.In this paper, we present efficient algorithms for solving several special cases of such multi-project scheduling problems with controllable project duration and hard resource constraints. Two types of problems are considered. In type I, the duration of each project includes a constant and a term that is inversely proportional to the amount of resource allocated. In type II, the duration of each individual project is a continuous decreasing function of the amount of resource allocated.