总延误问题顺时安排法的性能比

给定一组工件的加工时间与工期，要求确定这些工件在一台机器上的加．工排列，使相应的总延误达到最小，这就是总延误问题．该问题在近年已被证明是NP困难的．由Wilkermn和Irwin（1971），林勋（1983）等所研究的顺时安排法能得到相邻交换意义下的局部解．在本文中，我们进一步证明该算法能得到前移邻域意义下的局部解，并确定了该算法的性能比．     

带到达时间的单机排序中的资源分配问题

讨论两个单机排序的资源分配问题1｜rj,pj=bj-ajuj,Cmax≤｜∑uj和1｜rj,prec,pj=bj-ajuj C max≤｜∑uj并给出求其最优资源分配的多项式算法.     

A Hybrid Approach to Scheduling with Earliness and Tardiness Costs

A hybrid technique using constraint programming and linear programming is applied to the problem of scheduling with earliness and tardiness costs. The linear model maintains a set of relaxed optimal start times which are used to guide the constraint programming search heuristic. In addition, the constraint programming problem model employs the strong constraint propagation techniques responsible for many of the advances in constraint programming for scheduling in the past few years. Empirical results validate our approach and show, in particular, that creating and solving a subproblem containing only the activities with direct impact on the cost function and then using this solution in the main search, significantly increases the number of problems that can be solved to optimality while significantly decreasing the search time.     

CDMA蜂窝移动通信系统中的无线资源管理算法研究

无线资源管理是CDMA蜂窝移动通信系统保证业务质量(QoS)和提高频谱利用率的关键技术，本文提出了CDMA系统中无线资源管理算法的一般模型，阐述了三种重要的无线资源管理算法，即功率控制算法、呼叫接纳控制算法和分组调度算法的主要研究情况，并分析了目前研究中仍然存在和需要解决的问题。     

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （PART I：EQUAL TIMES AND COSTS）

Most papers in scheduling research have treated individual job processing times as fixed parameters. However, in many practical situations, a manager may control processing time by realloeating resources. In this paper, authors consider a machine scheduling problemwith controllable processing times. In the first part of this paper, a special case where the pro-cessing times and compression costs are uniform among jobs is discussed. Theoretical results are derived that aid in developing an O（n^2) algorithm to slove the problem optimally. In the second part of this paper, authors generalize the discussion to general case, An effective heuristic to the genera/ problem will be presented.     

The course scheduling problem at Lufthansa Technical Training

Lufthansa Technical Training GmbH (LTT) performs training courses for Lufthansa Technik AG as well as for several other international airlines. Courses of about 670 different types are offered of which several hundred take place each year. The course scheduling problem faced by LTT is to construct a yearly schedule which maximizes the profit margin incurred while meeting a variety of complex precedence, temporal, and resource-related constraints. A “good” operational schedule should also meet a number of additional subordinate objectives. We formalize the problem and develop a heuristic scheme along with several priority rules, as well as a local search algorithm to determine well-suited weights for weighted composite rules. The operational planning situation of 1996 served as our major test instance; additional test instances were constructed by modifying this data. Several computational experiments were carried out to evaluate the performance of the algorithms. It turned out that the best so-found schedule is substantially better in terms of the profit margin incurred than the solution manually constructed by LTT.     

A preemptive repeat priority queue with resampling: Performance analysis

In this paper, we analyze a discrete-time preemptive repeat priority queue with resampling. High-priority packets have preemptive repeat priority, and interrupted low-priority packets are subjected to independent retransmission attempts. Both classes contain packets with generally distributed transmission times. We show that the use of generating functions is beneficial for analyzing the system contents and packet delay of both classes. The influence of the priority scheduling on the performance measures is illustrated by some numerical examples. This work has been supported by the Interuniversity Attraction Poles Programme–Belgian Science Policy.     

Fast neighborhood search for the single machine total weighted tardiness problem

Most successful heuristics for solving 1||∑w_jT_j are based on swap moves. We present an algorithm which improves the complexity of searching the swap neighborhood from O(n³) to O(n²). We show that this result also improves the complexity of the recently developed dynasearch heuristics.     

基于遗传禁忌算法的双资源约束下并行生产线调度研究

并行生产线调度问题兼有并行机器和流程车间调度问题的特点,是一类新型的调度问题。在考虑遗传算法早熟收敛特性和禁忌搜索法自适应优点的基础上,将遗传算法和禁忌搜索法结合起来,提出了基于遗传算法和禁忌搜索算法的双资源并行作业车间的调度优化问题算法,即考虑到了产品的调度受到机器、工人等资源制约的影响,对算法中种群的构造,适应度计算,遗传操作等方面进行了研究,最后给出了实例仿真和结论。     

Asymptotic properties of constrained Markov Decision Processes

We present in this paper several asymptotic properties of constrained Markov Decision Processes (MDPs) with a countable state space. We treat both the discounted and the expected average cost, with unbounded cost. We are interested in (1) the convergence of finite horizon MDPs to the infinite horizon MDP, (2) convergence of MDPs with a truncated state space to the problem with infinite state space, (3) convergence of MDPs as the discount factor goes to a limit. In all these cases we establish the convergence of optimal values and policies. Moreover, based on the optimal policy for the limiting problem, we construct policies which are almost optimal for the other (approximating) problems. Based on the convergence of MDPs with a truncated state space to the problem with infinite state space, we show that an optimal stationary policy exists such that the number of randomisations it uses is less or equal to the number of constraints plus one. We finally apply the results to a dynamic scheduling problem.This work was partially supported by the Chateaubriand fellowship from the French embassy in Israel and by the European Grant BRA-QMIPS of CEC DG XIII