加工时间依赖工件位置的树约束单机排序问题

讨论了工件的加工时间依赖于工件位置的树约束单机排序问题,给出了目标函数为最大完工时间的多项式算法.结果表明,最大家庭树中的工件优先于其它家庭树中的工件加工,并且其工件要连续加工所得到的排序为最优排序.     

JIT方式下的单机分批调度问题的一种算法

在现代生产管理中,合理安排工件的加工顺序使所有的工件准时完工极为重要．文中研究工件不允许拖期的单机分批调度问题,目标是使加工．总成本最小,目标函数不仅考虑了工件提前完工有提前惩罚成本,还考虑了批加工成本费用．提出了一种多项式时间的最优算法．     

预防性周期维护下考虑可中断工件的再制造单机调度(英文)

研究预防性周期维护策略下再制造系统中可中断和不可中断2类工件的单机调度问题.以最小化完工时间为目标,提出了LPT-LS算法,该算法首先按LPT(longest processing time)规则安排不可中断工件,然后按LS(list scheduling)规则安排可中断工件.并根据可中断工件的总加工时间(记为S2)分3种情况证明了该算法的最坏情况比,结论如下:当S2大于按LPT规则安排不可中断工件后机器的空闲时间时,最坏情况比为1;当S2介于分别按LPT规则和OPT(最优排序)规则安排不可中断工件后机器的空闲时间之间时,最坏情况比小于2;当S2小于按OPT规则安排不可中断工件后机器的空闲时间时,最坏情况比小于2.最后通过算例验证了结论的正确性.     

工件可拒绝的单机无界平行批排序

首次考虑了目标函数为极小化最大延误与被拒绝工件的惩罚费用之和的单机无界平行批排序问题.证明了问题1｜B≥n,rej｜ Tmax+ TCP为NP-困难的,针对该问题给出了基于动态规划的伪多项式时间算法.     

带学习效应的单机成组排序问题

考虑了在工件具有学习效应的条件下,目标函数为最大完工时间和总完工时间的单机成组排序问题.对这两个问题分别给出了多项式时问算法并证明了其算法的最优性.     

工件加工排序问题的研究

通过对在给定设备、按规定工序下多种工件加工排序问题的研究,得出了基于最短加工时间规则和优化加工顺序规则基础上的工件加工排序模型。该模型按工件加工时间长短,从短到长顺序排列,同时要求最紧张设备等待时间最小化。在设备等待时间最小化的前提下,优先加工在该设备上加工时间最短的工件,兼顾启发性的搜索方法,使平均流程时间最短。最后通过实例分析证实了该算法的有效性与实用性。     

蚂蜂窝中的数学模型

所谓数学模型就是从定量的角度出发,分析、研究一个实际问题,在深入调查研究、了解对象信息、作出简化假设、分析内在规律等工作的基础上,用数学的符号和语言,把它表述为数学式子,即数学模型;通过计算得到模型的结果,解释实际问题,并接受实际的检验。这个过程包括“模型准备、模型假设、模型建立、模型求解、模型分析”等过程。本文以蚂蜂窝中的数学模型为例,与各位同仁共同探讨进行“数学建模”的教学途径。     

阶梯过程上确界统计参数的计算

随机过程模型能较好描述截面抗力问题,但参数的增加会使问题的复杂程度进一步扩大,而阶梯过程描述结构荷载可较好解决上述问题．为更好对阶梯过程的模型进行可靠性分析,文章把荷载取值出现跳跃时间间隔假设为随机变量,利用积分方程给出了荷载最大值的分布函数Fη（t,x）和密度函数fη（t,x）,进一步得到η的均值和标准差的近似求法．     

工件带拒绝费用的单机排序问题

在经典排序模型中,我们往往假定机器必须加工所有的工件,并且它们的加工时间都是给定的。但是在许多现实的应用中,若某个工件的加工时间或者加工费用很大,我们就会考虑是否要加工该工件,我们既可以选择付出一定的费用而拒绝加工该工件也可以选择不付费而加工它。这时目标函数不再是传统的最大总完工时间,极小化最大完工时间,最大延迟等,而是要同时考虑费用,我们把这种排序称为可拒绝排序[1][2]。本文研究了工件带拒绝费用的单机分族分批排序问题。主要证明了问题1,sfg|family-jobs,rej|Cmax+∑j∈sej和1,sfg|family-jobs,rej,b|Cmax+jisej是NP-难的,给出了它们的近似算法。     

3台平行机上带有2个服务等级的离线负载均衡

排序问题是一类重要的组合最优化问题,在生产计划、计算机控制等领域有着广泛应用,一直是理论界研究热点.对带服务等级的3台平行机排序问题进行研究,每台机器和每个工件都有等级标号,每个工件只能被某台服务等级不高于该工件等级的机器加工,目标是最小化最大机器的完工时间.运用新的算法思想解决离线状态等级约束下的3台机器负载均衡问题...     

单机最小化加权总完工时间的产品加工问题

In this paper,a fabrication scheduling problem concerning the production of components at a single manufacturing facility was studied,in which the manufactured components are subsequently assembled into a finite number of end products. Each product was assumed to comprise a common component to all jobs and a unique component to itself.Common operations were processed in batches and each batch required a setup time.A product is completed when both its two operations have been processed and are available.The optimality criterion considered was the minimization of weighted flow time.For this scheduling problem,the optimal schedules were described in a weignted shortest processing time first(WSPT)order and two algorithms were constructed corresponding to the batch availability and item availability,respectively.     

带同类恶化工件机器排序的多用户模型

We consider a scheduling problem involving a single processor utilized by two customers with constant deteriorating jobs,i.e.,jobs whose processing times are an increasing function of their starting times.Traditionally,such scenarios are modeled by assuming that each customer has the same criterion.In practice,this assumption may not hold.Instead of using a single criterion,we examine the implications of minimizing an aggregate scheduling objective function in which jobs belonging to different customers are evaluated with their individual criteria.We examine three basic scheduling criteria:minimizing makespan,minimizing maximum lateness,and minimizing total weighted completion time.We demonstrate all the scheduling problems considered are polynomially solvable.     

蚁群动态调度算法在混流车间作业调度的应用

混流车间作业调度是实际生产环节中的一个重要问题,也是制造系统生产管理的核心,同时实际的生产系统是一个动态生产环境.文中提出蚁群动态调度算法,通过实例具体分析并且跟传统的启发式算法相比较,实验结果证明蚁群动态调度算法对混流车间作业调度问题有较优的加工路径.     

Deterministic and randomized scheduling problems under the lp norm on two identical machines

Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problem P2|decr|lp (p＞1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of the lp norm of every machine's load. It is shown that LS algorithm is optimal for any lp norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|lp and P2|decr|lp are presented.     

带学习效应的供应链排序算法研究

考虑了机器在加工工件时会具有学习效应这一实际条件,将具有单制造商的供应链排序推广到具有多制造商的供应链排序问题.以总的加权配送时间和配送费用达到最小作为目标,在分析解的最优性条件的基础上,分别给出问题在工件具有一致性权重和不分批配送假设下的最优算法,并分析算法的时间复杂性.最后给出该问题的近似值.     

关于简单线性恶化问题的平行机排序的一个全多项式逼近算法

In this paper, a parallel machine scheduling problem was considered , where the processing time of a job is a simple linear function of its starting time. The objective is to minimize makespan. A fully polynomial time approximation scheme for the problem of scheduling n deteriorating jobs on two identical machines was worked out. Furthermore, the result was generalized to the case of a fixed number of machines.     

Scheduling problems on tardiness penalty and earliness award with simply linear processing time

In this paper, a single-machine scheduling model with a given common due date and simple linear processing times was considered. The objective is the total weighted tardiness penalty and earliness award. Some polynomial time solvable cases for this problem are given. A dynamic programming algorithm was provided and a branch and bound algorithm for general case of the problem was provided based on a rapid method for estimating the lower bound.     

Algorithms for semi on-line multiprocessor scheduling problems

In the classical multiprocessor scheduling problems, it is assumed that the problems are considered in off-line or on-line environment. But in practice, problems are often not really off-line or on-line but somehow in between. This means that, with respect to the on-line problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi on-line ones. The authors studied two semi on-line multiprocessor scheduling problems, in which, the total processing time of all tasks is known in advance, or all processing times lie in a given interval. They proposed approximation algorithms for minimizing the makespan and analyzed their performance guarantee. The algorithms improve the known results for 3 or more processor cases in the literature. Project supported by the National Natural Science Foundation of China (Nos. 19701028 and 19971078) and National 973 Research Project of China.     

Processing Times Modeled by Reliability Systems with a Random Number of Spare Units

A processing job with high reliability of final results is requested. It is performed as a multi-stage process. The facility at each stage may work correctly or malfunction. To enter any subsequent stage a secure result from the previous stage is required. This leads to the necessity of duplication of jobs at each stage many (random number of) times to provide two coinciding results, and a successful and reliable end. Then the total processing time, the quality of total processing of the job and related characteristics are modeled like those in a reliability system with random redundancy. Some analogies with the conventional results in reliability theory apply. Optimization problems are formulated and examples from information traffic are shown.     

工件有优先约束和尺寸的单机分批排序问题

研究了工件有优先约束和尺寸大小关系的分批排序问题,这里目标函数为工件的极大完工时间,这类问题是NP—完备的.对工件加工时间相同和有特殊到达时间的情况给出了它的近似算法,并证明其最差性能比不超过2.