单机排序中一个极小最大绝对迟后问题

本文考虑n个工件在单机上加工的排序问题,工作j的预期开始加工时间和所需加工时间分别为αj,pj,应交工时间为dj=αj kpj d,这里的k(≥0),d是待定的变量,目标函数为极小化最大绝对迟后。本文首先考虑了该问题一些特殊情况的研究结果,然后在强一致性条件下证得此问题O(nlogn)可解。     

Approximation Schemes for Scheduling Jobs with Common Due Date on Parallel Machines to Minimize Total Tardiness

The problem of scheduling n nonpreemptive jobs having a common due date d on m, m 2, parallel identical machines to minimize total tardiness is studied. Approximability issues are discussed and two families of algorithms {A } and {B } are presented such that (T ⁰ – T*)/(T* + d) holds for any problem instance and any given > 0, where T* is the optimal solution value and T ⁰ is the value of the solution delivered by A or B . Algorithms A and B run in O(n ^2m / ^m–1) and O(n ^m+1/ ^m ) time, respectively, if m is a constant. For m = 2, algorithm A can be improved to run in O(n ³/) time.     

具有相同批容量和相同工期的单机准时分批排序问题

研究具有相同批容量和相同工期的单机准时分批排序问题.这里相同批容量是指每批加工的工件数相同且恰为b个.准时排序要求工件在工期准时完工,提前或误工均受到惩罚.在两种分批方式下进行排序:继列分批和平行分批.目标函数为最小化加权总绝对误差和加权非准时惩罚.这里的权重不是工件自身所拥有的,而是工件所在的批一旦排在某个位置所获得的位置权重.证明了这些问题均可在O(nlogn)时间内解决.     

Polynomial Time Approximation Scheme for Two Parallel Machines Scheduling with a Common Due Date to Maximize Early Work

We study the scheduling problem with a common due date on two parallel identical machines and the total early work criterion. The problem is known to be NP-hard. We prove a few dominance properties of optimal solutions of this problem. Their proposal was inspired by the results of some auxiliary computational experiments. Test were performed with the dynamic programming algorithm and list algorithms. Then, we propose the polynomial time approximation scheme, based on structuring problem input. Moreover, we discuss the relationship between the early work criterion and the related late work criterion. We compare the computational complexity and approximability of scheduling problems with both mentioned objective functions.     

工件具有相同加工时间和相同窗口交货期的单机E/T调度问题

研究工件具有相同的加工时间和相同的窗口交货期,目标函数是总费用函数的单机调度问题.给出了求解该问题的一个简洁的数学公式.     

Minimizing the Range of Lateness on a Single Machine

This paper gives an optimizing algorithm to minimize the range of lateness, that is the difference between the maximum and minimum lateness, of jobs in a single-machine sequencing problem. The procedure is based on a branch-and-bound technique. One example has been solved to illustrate the method.     

Single Machine Batch Scheduling Problem with Resource Dependent Setup and Processing Time in the Presence of Fuzzy Due Date

We consider a batch scheduling problem on a single machine which processes jobs with resource dependent setup and processing time in the presence of fuzzy due-dates given as follows:1. There are n independent non-preemptive and simultaneously available jobs processed on a single machine in batches. Each job j has a processing time and a due-date.2. All jobs in a batch are completed together upon the completion of the last job in the batch. The batch processing time is equal to the sum of the processing times of its jobs. A common machine setup time is required before the processing of each batch.3. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource.4. The due-date of each job is flexible. That is, a membership function describing non-decreasing satisfaction degree about completion time of each job is defined.5. Under above setting, we find an optimal batch sequence and resource values such that the total weighted resource consumption is minimized subject to meeting the job due-dates, and minimal satisfaction degree about each due-date of each job is maximized. But usually we cannot optimize two objectives at a time. So we seek non-dominated pairs i.e. the batch sequence and resource value, after defining dominance between solutions.A polynomial algorithm is constructed based on linear programming formulations of the corresponding problems.     

Improved Bounds for the Range of Lateness on a Single Machine

In a recent article, Gupta and Sen have developed an algorithm to minimize the range of lateness on a single machine. The algorithm is based on the branch-and-bound approach suggested by Townsend for single-machine problems with quadratic penalty functions of completion times. In this paper, a simple general result for regular composition of cost functions is presented, application of which improves the Gupta and Sen procedure.     

An Algorithm for Minimizing the Range of Lateness on a Single Machine

This paper considers the problem of minimizing the range of lateness on a single machine. All the algorithms in the literature for solving this problem are based on the branch-and-bound approach, which has an exponential time complexity. In this paper, we demonstrate that this problem can actually be solved in pseudo-polynomial time, and develop such an algorithm. Computational performance of this algorithm on problems with various sizes is provided.     

工件有交货期的两人合作排序博弈问题

随着社会发展与进步,合作共赢已经成为一种共识,但人们出于自身利益的考虑,在合作的过程中总是希望自身利益最大,这就是合作博弈.合作博弈研究的问题就是要找到一个恰当的收益分配方案,使参加合作的所有利益主体愿意合作.这里考虑两人合作共同加工一批有交货期的工件排序博弈问题.每人提供一台机器用于工件的加工,工件加工时间是开工时间的简单线性函数,以最小的最大延误作为加工成本.设计一个多项式时间动态规划算法寻找到一个合理的博弈解集,由合作双方在解集中选定最终的合作收益分配方案,即找到最终的博弈解.     

具有非对称模糊加工时间工期指派调度优化问题的一类加权模型及其求解算法

根据模糊变量截集所表达的信息的重要程度,建立了模糊环境下工期指派调度优化问题的一类加权模型,该模型中工件加工时间为非对称三角模糊数,目标函数为极小化提前完工惩罚和拖期完工惩罚和的加权可能性均值.证明了当工件加工时间具有相同宽度比时,模型是多项式可解的,并给出了求解的多项式算法.数值实验表明加权模型与现有的非加权模型相比能有效的降低总费用.     

不确定条件下双目标组批生产的交货期设置研究

交货期是调度方法的函数,因而具有不确定性.研究变批量、变批次、变生产能力下,单阶段、双目标有条件相容组批的交货期设置问题,将它转化为订单投放策略和调度模式研究.建立了一个基于目标的双目标订单投放策略数学模型.采用目标序列优先方法进行双目标求解,用两种调度模式求出区间值,进行最优交货期逼近.模式1:松弛掉产品加工约束条件,基于负荷考虑、给出离散生产模式下订单完工率最大的订单排序算法,算法综合考虑了任务紧急程度、可调度性、重要度和流程时间最短四个方面,得到区间的一个端点.模式2是有条件相容的启发式组批调度算法,即通过聚类计算将订单安排问题转化为多队列调度问题,将新来订单的投放转化为某个队列的插单和批量分割问题,不同队列中批的投产顺序由批中优先级最高的订单决定,并在能力约束下进行批量分割计算,得到区间的另一个端点,结合流程可靠性求出区间.实例证明,模式2的交货期设置小,订单完工率和生产率高.     

Single Machine Scheduling with a Common Delivery Window

In this paper we consider the single machine scheduling problem of minimizing the mean absolute deviation (MAD) of job completion times from a restricted common delivery window. This problem is NP-hard. A Lagrangian relaxation procedure is proposed to solve the problem. Two efficient heuristics are also proposed. An experimental study on randomly generated problems is carried out to test the performance of the proposed methods. The computational results show that the obtained lower bounds are very good and the proposed heuristics generate near-optimal solutions.     

遗传算法求解带容量限制的最小费用流问题

研究了带容量限制的带固定费用和可变费用的最小费用流问题,发现该问题是混合0-1整数规划问题,不存在多项式算法.在研究了最优解的结构后,结合最优解的结构特点为之设计了遗传算法,然后构造了一个100个节点的特殊网络,用计算机做了100例计算,验证了该算法具有很好的近似比和很快的收敛速度.     

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

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

A Class of Single Step Methods with a Large Interval of Absolute Stability

In this paper, a class of integration formulas is derived from the approximation so that the first derivative can be expressed within an interval $[nh,(n+1)h]$ as $$\frac{dy}{dt}=-P(y-y_n)+f_n+Q_n(t).$$ The class of formulas is exact if the differential equation has the shown form, where $P$ is a diagonal matrix, whose elements $$-pj=\frac{\partial}{\partial y_j}f_j(t_n,y_n),j=1,\cdots,m$$ are constant in the interval $[nh,(n+1)h]$, and $Q_n(t)$ is a polynomial in $t$. Each of the formulas derived in this paper includes only the first derivative $f$ and $$-pj=\frac{\partial}{\partial y_j}f_j(t_n,y_n).$$ It is identical with a certain Runge-Kutta method. In particular, when $Q_n(t)$ is a polynomial of degree two, one of our formulas is an extension of Treanor's method, and possesses better stability properties. Therefore the formulas derived in this paper can be regarded as a modified or an extended form of the classical Runge-Kutta methods. Preliminary numerical results indicate that our fourth order formula is superior to Treanor's in stability properties.     

一类脉冲控制模型的最小费用问题

本文研究了一类脉冲控制模型的最小费用问题,在一定条件下,给出了相应的最佳费用函数具体解析式．     

Shape Methods for the Transmission Problem with a Single Measurement

In the current work, we consider the inverse conductivity problem of recovering inclusion with one measurement. First, we use conformal mapping techniques for determining the location of the anomaly and estimating its size. We then get a good initial guess for quasi-Newton type method. The inverse problem is treated from the shape optimization point of view. We give a rigorous proof for the existence of the derivative of the state function and of shape functionals. We consider both least squares fitting and Kohn and Vogelius functionals. For the numerical implementation, we use a parameterization of shapes coupled with a boundary element method. Several numerical examples indicate the superiority of the Kohn and Vogelius functional over least squares fitting.     

带运输时间和自动机的法流水作业排序问题的复杂性

研究目标函数为使最大完工时间达到最小的三台机器情况下的流水作业排序问题,同一工件在某台机器上完工后和在下一台机器上开始加工这段时间内,存在称为运输时间的时间间隔,所有的运输工作均由自动机来完成,自动机在同一时间内最多运输一个工件,文章研究该问题及其特殊情况下的复杂性.     

一种双目标带约束工件成类的平行机器调度启发式规则

提出了一种快速而有效的启发式规则(fam ily slack,简称FSLACK),来求解极小化总延误时间和极小化最大完工时间两个目标,工件按产品类型成组,带模具数量约束的平行机器生产调度问题.本文提出的FSLACK与EDD、LPT及SLACK进行了比较.随机订单的测试结果表明,本文提出的启发式规则在求解双目标带约束工件成类的平行机器调度问题上是有效的.这表明该算法可以应用在成型加工业的现场作业调度.