可换速平行机工件带起止值的抢先进度表

本文讨论可换速平行机工件带起止值的抢先进度表模型,给出了工件在可换速平行机上存在可行的抢先进度表的充要条件;给出了一个以Ｏ（ｍ~（７／３）ｎ~３＋ｂｌｏｇｂ）为界的算法来构造一个可行的抢先进度表．     

具有优先约束的不完全恒速机排序问题

讨论了任务具有优先约束的可中断不完全恒速机排序问题,若处理机具有不同开始加工时间的可中断排序问题存在最优算法,则相应的不完全恒速机排序问题也有最优算法。     

任务具有优先约束的不完全同速机排序问题

文中讨论了任务具有优先约束的不完全同速机排序问题，对问题Ｐｍ｜ｂｒｋｄｗｎ，ｉｎｔｒｅｅ，ｐｊ＝１｜Ｃｍａｘ给出了最优算法，对问题Ｐｍ｜ｂｒｋｄｗｎ，ｐｒｅｃ，ｐｊ＝１｜Ｃｍａｘ给出了界为２－２ｍ的算法。     

Scheduling Tasks with Small Communication Delays for Clusters of Processors

The labor tour scheduling literature has focused on the development of schedules, and with a few exceptions, employees were assumed to have identical cost and productivity. Even the few exceptions in the literature that solved tour problems considered employees within a work group to have identical cost and productivity. In this paper we evaluated heuristics for assigning individual employees – who differed in cost and productivity – to labor tour schedules. Our results showed that considering productivity levels when assigning individuals to tours increased profitability. We found that a simple managerial heuristic of assigning individuals in descending order of their productivity to cost ratio was both fast and effective over a broad range of service environmental scenarios.     

Scheduling Malleable Tasks on Parallel Processors to Minimize the Makespan

The problem of optimal scheduling n tasks in a parallel processor system is studied. The tasks are malleable, i.e., a task may be executed by several processors simultaneously and the processing speed of a task is a nonlinear function of the number of processors allocated to it. The total number of processors is m and it is an upper bound on the number of processors that can be used by all the tasks simultaneously. It is assumed that the number of processors is sufficient to process all the tasks simultaneously, i.e. n≤m. The objective is to find a task schedule and a processor allocation such that the overall task completion time, i.e. the makespan, is minimized. The problem is motivated by real-life applications of parallel computer systems in scientific computing of highly parallelizable tasks. An O(n) algorithm is presented to solve this problem when all the processing speed functions are convex. If these functions are all concave and the number of tasks is a constant, the problem can be solved in polynomial time. A relaxed problem, in which the number of processors allocated to each task is not required to be integer, can be solved in O(nmax {m,nlog ² m}) time. It is proved that the minimum makespan values for the original and relaxed problems coincide. For n=2 or n=3, an optimal solution for the relaxed problem can be converted into an optimal solution for the original problem in a constant time.     

Online Scheduling with Hard Deadlines

We study non-preemptive, online admission control in the hard deadline model: each job must either be serviced prior to its deadline or be rejected. Our setting consists of a single resource that services an online sequence of jobs; each job has a length indicating the length of time for which it needs the resource and a delay indicating the maximum time it can wait for the service to be started. The goal is to maximize total resource utilization. The jobs are non-preemptive and exclusive, meaning once a job begins, it runs to completion, and at most one job can use the resource at any time. We obtain a series of results, under varying assumptions of job lengths and delays.     

带强制工期的可中断单机排序问题

工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.本文讨论了在单机上,加工带准备时间与强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过奇偶划分问题归约,证明了其是NP-complete的.而后,讨论了加工时间相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序,因此提出了—个多项式时间算法,既能判定可行性,又能针对可行问题获得最优排序.     

一类速度不同的具有m台通用机的n组工件的排序问题

研究的目的在于解决实践中对多组任务的优化排序问题,即在最短的时间内完成所有给定的任务,由于这类问题往往都是NP完全问题,人们通常寻求其近似算法．文中提出了一种改进的LPT算法,利用。首先空闲”准则,讨论了将n组工件安排在n台速度不同的专用机,m台速度小于专用机的通用机上的C‰。。问题,得到了利用该近似算法所得的解T与最优解T＊的—个估计：T/T＊≤2＋（n-2）/（m＋1）     

Little-Preemptive Scheduling on Unrelated Processors

We consider the preemptive scheduling of n independent jobs on m unrelated machines to minimize the makespan. Preemptive schedules with at most 2m–3 preemptions are built, which are optimal when the maximal job processing time is no more than the optimal schedule makespan. We further restrict the maximal job processing time and obtain optimal schedules with at most m–1 preemptions. This is better than the earlier known best bound of 4m ²–5m+2 on the total number of preemptions. Without the restriction on the maximal job processing time, our (2m–3)-preemptive schedules have a makespan which is no more than either of the following two magnitudes: (a) the maximum between the longest job processing time and the optimal preemptive makespan, and (b) the optimal nonpreemptive makespan. Our (m–1)-preemptive schedules might be at most twice worse than an optimal one.     

Randomized On-Line Scheduling Similar Jobs to Minimize Makespan on Two Identical Processors

In this paper we consider an on-line scheduling problem, where jobs with similar processing times within [1, r] arrive one by one to be scheduled in an on-line setting on two identical parallel processors without preemption. The objective is to nlinimize makespan. We devise a randomized on-line algorithm for this problem along with a lower bound.     

An Application of the Bin-packing Technique to Job Scheduling on Uniform Processors

A non-polynomial algorithm is presented for solving the minimum makespan problem on a set of uniform machines. This algorithm uses the bin-packing technique and provides an approximate solution which turns into an optimal one when the relative error is chosen small enough.     

Scheduling Tasks on Unrelated Machines: Large Neighborhood Improvement Procedures

Two approximation algorithms are presented for minimizing the makespan of independant tasks assigned on unrelated machines. The first one is based upon a partial and heuristical exploration of a search tree, which is used not only to build a solution but also to improve it thanks to a post-optimization procedure. The second implements a new large neighborhood improvement procedure to an already existing algorithm. Computational experiments show that their efficiency is equivalent to the best local search heuristics.     

具有通用机的n组工件的排序问题

本文讨论了具有n台速度相同的专用机,一台同速度的通用机的n组工件的Cmax问题,提出了改进的LPT算法,得到了近似算法的一个估计．     

A Tandem Queue with Coupled Processors: Computational Issues

In Resing and Örmeci [16] it is shown that the two-stage tandem queue with coupled processors can be solved using the theory of boundary value problems. In this paper we consider the issues that arise when calculating performance measures like the mean queue length and the fraction of time a station is empty. It is assumed that jobs arrive at the first station according to a Poisson process and require service at both stations before leaving the system. The amount of work that a job requires at each of the stations is an independent, exponentially distributed random variable. When both stations are nonempty, the total service capacity is shared among the stations according to fixed proportions. When one of the stations becomes empty, the total service capacity is given to the nonempty station. We study the two-dimensional Markov process representing the numbers of jobs at the two stations. The problem of finding the generating function of the stationary distribution can be reduced to two different Riemann-Hilbert boundary value problems, where both problems yield a complete analytical solution. We discuss the similarities and differences between the two problems, and relate them to the computational aspects of obtaining performance measures.     

Scheduling with uncertainties on new computing platforms

New distributed computing platforms (grids) are based on interconnections of a large number of processing elements. A most important issue for their effective utilization is the optimal use of resources through proper task scheduling. It consists of allocating the tasks of a parallel program to processors on the platform and to determine at what time the tasks will start their execution. As data may be subject to uncertainties or disturbances, it is practically impossible to precisely predict the input parameters of the task scheduling problem.     

Scheduling with safety distances

We investigate the problem of Scheduling with Safety Distances (SSD) that consists in scheduling jobs on two parallel machines without machine idle time. Every job is already assigned to its machine, and we just have to specify an ordering of the jobs for each machine. The goal is to find orderings of the jobs such that the minimum time elapsed between any two job completion times is maximized. We prove that this problem is NP-hard in general and give polynomial time algorithms for special cases. These results combined establish a sharp borderline between NP-complete and polynomial solvable versions of the problem SSD.This research was supported by the Christian Doppler Laboratorium für Diskrete Optimierung.On leave from the Mathematics Section, Forestry University Nanjing, Nanjing, PR China.     

Scheduling with few changes

In this work we consider scheduling problems where a sequence of assignments from products to machines – or from tasks to operators, or from workers to resources – has to be determined, with the goal of minimizing the costs (=money, manpower, and/or time) that are incurred by the interplay between those assignments. To account for the different practical requirements (e.g. few changes between different products/tasks on the same machine/operator, few production disruptions, or few changes of the same worker between different resources), we employ different objective functions that are all based on elementary combinatorial properties of the schedule matrix. We propose simple and efficient algorithms to solve the corresponding optimization problems, and provide hardness results where such algorithms most likely do not exist.     

基于约束满足问题的中继卫星调度问题研究

中继卫星任务规划与调度是中继卫星系统应用中的重要问题。根据航天器的空间轨道参数，得到中继卫星与用户航天器之间的可见时间窗口。在此基础上，通过分析中继卫星系统中各种资源之间的约束关系、任务优先级与调度准则，建立中继卫星系统的任务调度模型。仿真结果表明，基于约束规划理论建立中继卫星调度模型是解决中继卫星调度问题的有效方法。     

Scheduling with job delivery coordination on single machine

This paper investigates a single machine scheduling problem with job delivery coordination, in which each job demands different amount of storage space during transportation. In this problem, a set of independent jobs from a customer must first be processed on a machine without preemption and then delivered by two homogeneous vehicles to the customer in batches. To minimize the makespan, we develop a best possible polynomial-time heuristic with a worst-case ratio of 2.     

Scheduling tasks with communication delays on parallel processors

LetP={v ₁,...,v _n } be a set ofn jobs to be executed on a set ofm identical machines. In many instances of scheduling problems, if a jobv _i has to be executed before the jobv _j and both jobs are to be executed on different machines, some sort of information exchange has to take place between the machines executing them. The time it takes for this exchange of information is called a communication delay.In this paper we give anO(n) algorithm to find an optimal scheduling with communication delays when the number of machines is not limited and the precedence constraints on the jobs form a tree.