工件加工时间恶化问题的若干研究

主要研究关于工件加工时间恶化的若干问题,给出了最大完工时间问题的一些性质、总完工时间问题的算法和性质,并根据实际问题,设计了一些新模型,相应地给出了该问题所具有的性质及一些简单算法．     

线性时间复杂度排序算法研究及应用

算法在程序设计中起着至关重要的作用,一个好的算法可以让程序变得高效。排序作为数据处理最基本的工作之一,在程序中需要大量使用。常见的几种排序算法的平均时间复杂度最优为O(nlog2n),为从根本上提高程序的运行效率,对能够在线性时间解决数据排序的算法进行了研究,并在实际问题中对桶排序算法加以了应用。     

两个带机器准备时间的半在线排序

研究两个带机器准备时间的半在线排序算法,一个是当总加工时间已知时,工件在有准备时间的同类机上加工的半在线排序,证明了其竞争比的上下界分别为2ν和ν+1/2ν+1,都与机器加工速度有关;另一个是当最大加工时间已知时,工件在有准备时间的同型机上加工的半在线排序,证明了其竞争比为2/3.     

机器有两种不同速度的平行工件半在线排序研究

本文提出了新模型Q2m︱rj=0,on-line-ncv︱C max,并通过分析模型的特点,设计出了半在线算法,引进等效化(Virtualization)概念证明了当P≥m(s+1)max/(i∈τ)mjPj时(其中P为工件集的总负荷),算法的竞争比为2-s/(m(s+1)).     

加工时间相同的分族分批排序加权总完工时间问题

考虑极小化加权总完工时间的单机分族分批排序问题,给出了最优排序的性质和算法,并加以证明,对工件有k个到达时间的情形,给出了一个复杂性为O(2k-1nlogn)的启发式算法.     

一类无界的不相容工件族分批排序加权总完工时间问题

考虑极小化加权总完工时间的一类无界的不相容工件族分批排序问题,给出了最优排序的性质和算法,并加以证明．对工件有k个到达时间的情形,给出了一个复杂性为D（2^k-1nlogn）的启发式算法．     

排序算法时间复杂度的研究

算法设计的好坏直接影响计算机的运行时间，计算机排序方法较多，时间复杂度差别较大．本文从理论上研究了线性排序(选择法、冒泡法、计数法)、比较排序、堆排序和快速排序等几种常用的排序算法的时间复杂度．     

两台同类机极小化总完工时间的分批排序问题

考虑了两台同类机极小化总完工时间的分批排序问题,给出了计算复杂性为O(n3)的动态规划算法,并将此算法推广到了工件具有学习效应的情况.     

排序算法时间复杂度研究

分析了选择排序、交换排序和插入排序三类算法,对直接选择排序、堆排序、冒泡排序、快速排序、直接插入排序和希尔排序算法进行了深入研究,论证了在最好情况、平均情况和最坏情况下这些算法的时间复杂度。     

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

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.     

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

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.     

与开工时间有关的加工时间的超前有奖迟后受罚的排序问题的动态规划算法

In this paper, a single-machine scheduling model with a given common due date is considered. Job processing time is a linear decreasing function of its starting time. The objective function is to minimize the total weighted earliness award and tardiness penalty. Our aim is to find an optimal schedule so as to minimize the objective function. As the problem is NP-hard, some properties and polynomial time solvable cases of this problem are given. A dynamic programming algorithm for the general case of the problem is provided.     

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.     

Genetic algorithm for scheduling reentrant jobs on parallel machines with a remote server

This paper considers a reentrant scheduling problem on parallel primary machines with a remote server machine, which is required to carry out the setup operation. In this problem, each job has three operations. The first and last operations are performed by the same primary machine, implying the reentrance, and the second operation is processed on the single server machine. The order of jobs is predetermined in our context. The challenge is to assign jobs to the primary machines to minimize the makespan. We develop a genetic algorithm（GA） to solve this problem. Based on a simple strategy of assigning jobs in batches on the parallel primary machines, the standardized random key vector representation is employed to split the jobs into batches. Comparisons among the proposed algorithm, the branch and bound（BB） algorithm and the heuristic algorithm, coordinated scheduling（CS）, which is only one heuristic algorithm to solve this problem in the literature, are made on the benchmark data. The computational experiments show that the proposed genetic algorithm outperforms the heuristic CS and the maximum relative improvement rate in the makespan is 1.66%.     

Semi On-line Scheduling Problem for Maximizing the Minimum Machine Completion Time on m Identical Machines

In this paper, a semi on-line version on m identical machines M1 , M2, …, Mm ( m ≥ 3 ) was considered, where the processing time of the largest job is known in advance. Our goal is to maximize the minimum machine load, an NPLS algorithm was presented and its worst-case ratio was proved to be equal to m - 1 which is the best possible value. It is concluded that if the total processing time of jobs is also known to be greater than (2 m - 1 )Pmax where pmax is the largest job‘s processing time, then the worstcase ratio is 2 - 1/m.     

具有机器适用性约束的相同工件平行机近似调度算法

针对考虑机器适用性的相同工件平行机调度问题,提出1种二阶段近似调度算法。算法建立了问题的半匹配模型G=[J∪M,E,W],将原问题转化为最优半匹配搜索问题,然后通过初始解构造和优化得到问题的近似解。通过分析G=[J∪M,E,W]的拓扑统计信息对机器均载的影响,设计了初始解构造启发式规则。在此基础上,采用贪心原理,提出了基于启发式规则的初始解构造算法。初始解优化算法以初始解为起点,采用基于交错路径的局部优化方法得到近似解。通过交错路径树,搜索最优交错路径是影响初始解优化算法的重要因素。为提高搜索效率,限定交错路径的最大长度为4。最后,从理论上分析了算法的最坏情况界和时间复杂度。     

Semi On-line Scheduling Problem for Maximizing the Minimum Machine Completion Time on mIdentical Machines

1　Introduction　In this paper, we consider a semi on line version onm identical machines M1, M2, …, Mm (m ≥3 )where the processing time of the largest job is knownin advance. A list (j1, j2, …, jn ) of jobs withprocessing times p1, p2, …, pn is given on line,which means we get the jobs one by one but both thetotal number of jobs that need to be scheduled and thesize of the jobs are not previously known. Theprocessing time of job ji becomes known only whenji-1 has…     

A new heuristic algorithm for general integer linear programming problems

1 Introduction ? Since the cutting plane method [1] and branch-and- bound principle [2] were developed as two types of efficient approaches for integer linear programming problems, how to improve them or to find new algorithms more efficient has become an…     

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

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.