基于控制工序性质的LOB截止日期问题分析与算法

截止日期问题是重复性项目调度中研究最为广泛的问题之一,其旨在满足项目截止日期前提下求得一个工作队雇佣总量最小的调度方案。由于重复性项目往往为大型工程建设项目,一个准确的最优进度计划对于节约项目的资源和成本具有重要意义。在平衡线法(LOB)框架下,本文从控制工序的性质出发,研究并分析了控制工序工作队分配与项目总工期之间的关联,给出了截止日期问题的一些特殊性质。基于这些性质,一方面能够帮助项目管理人员判断一个调度方案是否可行且经济,另一方面能够得到一些有效的剪枝策略,从而设计出具有针对性的分支限界算法。最后,通过案例计算和仿真实验验证了本文提出的算法在计算效果和计算效率上的有效性。     

Convex comparison of service disciplines in real time queues

We present a comparison of the service disciplines in real time queueing systems (the customers have a deadline before which they should enter the service booth). We state that giving priority to customers having an early deadline minimizes the average stationary lateness. We show this result by comparing adequate random vectors with the Schur convex majorization ordering.     

A hybrid imperialist competitive algorithm for minimizing makespan in a multi-processor open shop

In this paper a new mixed-integer linear programming (MILP) model is proposed for the multi-processor open shop scheduling (MPOS) problems to minimize the makespan with considering independent setup time and sequence dependent removal time. A hybrid imperialist competitive algorithm (ICA) with genetic algorithm (GA) is presented to solve this problem. The parameters of the proposed algorithm are tuned by response surface methodology (RSM). The performance of the algorithm to solve small, medium and large sized instances of the problem is evaluated by introducing two performance metrics. The quality of obtained solutions is compared with that of the optimal solutions for small sized instances and with the lower bounds for medium sized instances. Also some computational results are presented for large sized instances.     

Asset-selling problem with an uncertain deadline,quitting offer,and search skipping option

This paper presents a discrete-time sequential stochastic asset-selling problem with an infinite planning horizon, where the process of selling the asset may reach a deadline at any point in time with a probability. It is assumed that a quitting offer is available at every point in time and search skipping is permitted. Thus, decisions must be made as to whether or not to accept the quitting offer, to accept an appearing buyer’s offer, and to conduct a search for a buyer. The main purpose of this paper is to clarify the properties of the optimal decision rules in relation to the model’s parameters.     

柔性工期下的资源受限项目调度双目标优化研究

在项目调度过程中,活动工期应根据项目截止工期以及资源供给情况进行合理设置,而在传统的资源受限项目调度问题(RCPSP)中,活动的工期往往是已知且固定的,这在一定程度上限制了项目调度的灵活性。多模式下的项目调度方式虽然弥补了这一缺点,但其提供的工期-资源组合种类固定且有限,并不一定能保证包含最优的工期-资源组合。本文将活动工期作为项目调度问题的决策变量,允许其在一定范围内取值。这种柔性工期调度方式虽然增加了项目调度难度,但提高了项目调度灵活性,同时可以起到压缩项目完工时间的作用。为验证柔性工期调度方式对项目工期和成本的影响,本文建立了工期-成本双目标权衡优化模型,设计了两阶段嵌套算法(NSGAⅡ-RS)对其求解,实验证明,柔性工期调度策略是一种鲁棒性较好的项目完工时间压缩策略。     

城市消防站点布局的改进启发式算法

面对数量较多需要及时处理的突发事故,为了满足最短应急时间限制,最低应急资源数和最少的出救点等目标,在城市规划决策中,考虑在一个确定应急限制期下的安全消防站选址问题,给出一个反映决策者对时间和费用偏好的折衷选址方案十分必要.从实际应用出发,运用改进启发式算法方法研究时间与资源限制条件下的多出救点组合模型求解问题.给出了应急限制期和安全消防设施点建立的费用模型,从理论上证明了模型求解方法的正确性.在给定限制期条件下,通过分析得出应急服务设施点选择方法.通过算例说明该计算方法的具体应用,为交通安全消防站点选择提供参考,该方法还适用于诸如医院急救站等类似公共设施的规划建设.     

Scheduling of Jobs in a Hypercube Processing System

When a job is processed in a hypercube multi-processor, it is allocated a cube of processing elements of the requisite size. There are three distinct costs involved in the hypercube scheduling problem: the cost of detecting a free cube (allocation), the cost of migrating jobs and merging the free spaces to accommodate a larger cube request (relocation) and the cost of not meeting the due date (tardiness). Traditionally, research in this area has focused on finding efficient algorithms for allocating a free cube (if any) in the hypercube system. The relocation cost has been treated as an independent cost metric. The role of scheduling has not received much attention and present subcube allocation methods assume a first-come-first-serve (FCFS) approach over the input job set.This paper considers the underlying scheduling issues in a hypercube processing system and shows how techniques other than FCFS scheduling of the incoming jobs can help in reducing the relocation cost and hence the overall subcube resource assignment cost. We discuss five simple and easily implementable dispatching heuristics, and compare their relative performance with the FCFS scheduling rule to demonstrate the advantages of scheduling in subcube allocation.     

自回归条件异方差模型在宏观经济预警中的应用

将ＡＲＣＨ模型引入宏观经济预警，讨论了ＡＲＣＨ预警系统的指标设计、ＡＲＣＨ预警方法以及预警警限的界定，给出了一种具有ＡＲＣＨ特征的警限界定方法。     

Algorithm for minimizing weighted earliness penalty in single-machine problem

In this paper, the problem of minimizing the weighted earliness penalty in a single-machine scheduling problem is addressed. For this problem, every job is assumed to be available at time zero and must be completed before or on its deadline. No tardy job is allowed. Each job has its own earliness penalty and deadline. The paper identifies several local optimality conditions for sequencing of adjacent jobs. A heuristic algorithm is developed based on these local optimality conditions. Sample problems are solved and the solutions obtained from the heuristic are compared to solutions obtained from the heuristics developed by Chand and Schneeberger. Also, comparisons are performed between the solutions obtained from the heuristic and the optimal solutions obtained from a mathematical modeling approach for problems involving 10 and 15 jobs. The results show that the developed heuristic produces solutions close to optimal in small size problems, and it also outperforms the Chand and Schneeberger's method.     

Scheduling real-time tasks for dependability

Real-time systems are increasingly used in applications whose failure may result in large economic and human costs. Since many such systems operate in environments that are non-deterministic, and possibly hazardous, it is extremely important that the systems be dependable, namely the deadlines of tasks must be met even in the presence of particular failures. In order to enhance the dependability of a real-time system, we study the problem of scheduling a set of real-time tasks to meet their deadlines in the presence of processor failures. We first prove that the problem of scheduling a set of non-preemptive tasks on more than two processors to tolerate one arbitrary processor failure is NP-complete even when the tasks share a common deadline. Heuristic algorithms are then proposed to solve this problem. The schedules generated by the heuristic algorithms can tolerate one arbitrary processor failure in the worst case. The analysis and experimental data show that the performance of the algorithms is near-optimal.     

Real-time queueing theory: A tutorial presentation with an admission control application

Real-time scheduling, or scheduling with respect to a deadline, is critical in many application areas such as telecommunications, control systems, and manufacturing. This paper presents a novel approach to real-time scheduling based on a queueing theory model. Using real-time queueing theory (RTQT), one can analytically determine the distribution of the lead-time profile (i.e., the time until the deadline is reached) of customers waiting for service. Emphasis is placed on the development of the equations used to determine the lead-time profile distribution. The development of the GI/G/1 case is presented and confirmed using simulation. Simulation results confirm prior research for the M/M/1 and GI/M/1 case. As a practical application, RTQT is used to implement a packet admission control algorithm for a telecommunications network. Using this algorithm, packet lateness was reduced by up to 31%. This revised version was published online in June 2006 with corrections to the Cover Date.     

On queueing with customer impatience until the beginning of service

We study queueing systems where customers have strict deadlines until the beginning of their service. An analytic method is given for the analysis of a class of such queues, namely, models. These are queues with state-dependent Poisson arrival process, exponential service times, multiple servers, FCFS service discipline, and general customer impatience. The state of the system is viewed to be the number of customers in the system. The principal measure of performance is the probability measure induced by the offered waiting time. Other measures of interest are the probability of missing deadline and the probability of blocking. Closed-form solutions are derived for the steady-state probabilities of the state process and some important modeling variables and parameters. The efficacy of our method is illustrated through a numerical example. This revised version was published online in June 2006 with corrections to the Cover Date.     

用随机模糊方法研究合理确定工程项目工期

站在兼顾业主与建造商的公正立场,基于网络优化技术基础上并以系统的观点,采用随机模糊数学方法研究合理确定项目工期,进而用实际项目进行分析验证,是一种科学合理确定工期的方法.     

Online time-constrained scheduling in linear and ring networks

We consider the problem of scheduling a sequence of packets over a linear network, where every packet has a source and a target, as well as a release time and a deadline by which it must arrive at its target. The model we consider is bufferless, where packets are not allowed to be buffered in nodes along their paths other than at their source. This model applies to optical networks where opto-electronic conversion is costly, and packets mostly travel through bufferless hops. The offline version of this problem was previously studied in M. Adler et al. (2002) [3]. In this paper we study the online version of the problem, where we are required to schedule the packets without knowledge of future packet arrivals. We use competitive analysis to evaluate the performance of our algorithms. We present the first online algorithms for several versions of the problem. For the problem of throughput maximization, where all packets have uniform weights, we give an algorithm with a logarithmic competitive ratio, and present some lower bounds. For other weight functions, we show algorithms that achieve optimal competitive ratios.     

占线订单排序C——收益函数下改进的随机策略

对于订单具有紧交货期限且以最大化完工总收益为目标的占线订单排序问题，Woeginger（1994）提出了完工收益与订单长度满足C——收益函数关系的一类模型，并给出了竞争比为4的最优确定性策略。本文针对该模型设计了一个简单的随机策略，并证明其具有竞争比2。该策略明显简单于已有的各种随机策略；同时，本文结论大大改进了Seiden（1998）所给出的当前最好竞争比3．732。     

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

讨论了在m台同型平行机上,加工带强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,讨论了强制工期相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序.先讨论了可行性,接着针对可行问题,提出一个算法在多项式时间内获得最优排序.     

Log-weight scheduling in switched networks

We consider switched queueing networks in which there are constraints on which queues may be served simultaneously. The scheduling policy for such a network specifies which queues to serve at any point in time. We introduce and study a variant of the popular maximum weight or backpressure policy which chooses the collection of queues to serve that has maximum weight. Unlike the maximum weight policies studied in the literature, the weight of a queue depends on logarithm of its queue-size in this paper. For any multihop switched network operating under such maximum log-weighted policy, we establish that the network Markov process is positive recurrent as long as it is underloaded. As the main result of this paper, a meaningful fluid model is established as the formal functional law of large numbers approximation. The fluid model is shown to be work-conserving. That is, work (or total queue-size) is nonincreasing as long as the network is underloaded or critically loaded. We identify invariant states or fixed points of the fluid model. When underloaded, null state is the unique invariant state. For a critically loaded fluid model, the space of invariant states is characterized as the solution space of an optimization problem whose objective is lexicographic ordering of total queue-size and the negative entropy of the queue state. An important contribution of this work is in overcoming the challenge presented by the log-weight function in establishing meaningful fluid model. Specifically, the known approaches in the literature primarily relied on the “scale invariance” property of the weight function that log-function does not possess.     

带强制工期的双机开放车间排序问题

讨论了强制工期相等的n个工件在双机开放车间加工.在允许机器空闲的条件下,寻找一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,同题可能会无可行排序.先讨论了问题的可行性.如果问题可行,找出一个可行序列作为预排序列,并提出了一个算法计算每个工件尽可能迟的开工时间.而后,提出了一个多项式时间最优算法,在预排序列的基础上,通过调整两台机器上最先加工的工件来获得最优排序.     

On scheduling a multiclass queue with abandonments under general delay costs

We consider a multiclass queueing system with abandonments and general delay costs. A system manager makes dynamic scheduling decisions to minimize long-run average delay and abandonment costs. We consider the three types of delay cost: (i) linear, (ii) convex, and (iii) convex–concave, where the last one corresponds to settings where customers may have a particular deadline in mind but once that deadline passes there is increasingly little difference in the added delay. The dynamic control problem for the queueing system is not tractable analytically. Therefore, we consider the system in the conventional heavy traffic regime and study the approximating Brownian control problem (BCP). We observe that the approximating BCP does not admit a pathwise solution due to abandonments. In particular, the celebrated cμ rule and its extension, the generalized cμ rule, which is asymptotically optimal under convex delay costs with no abandonments, are not optimal in this case. Consequently, we solve the associated Bellman equation, which yields a dynamic index policy (derived from the value function) as the optimal control for the approximating BCP. Interpreting that control in the context of the original queueing system, we propose practical policies for each of the three cases considered and demonstrate their effectiveness through a simulation study.     

Scatter search for project scheduling with resource availability cost

This paper considers a project scheduling problem with the objective of minimizing resource availability costs, taking into account a deadline for the project and precedence relations among the activities. Exact methods have been proposed for solving this problem, but we are not aware of existing heuristic methods. Scatter search is used to tackle this problem, and our implementation incorporates advanced strategies such as dynamic updating of the reference set, the use of frequency-based memory within the diversification generator, and a combination method based on path relinking. We also analyze the merit of employing a subset of different types when combining solutions. Extensive computational experiments involving more than 2400 instances are performed. For small instances, the performance of the proposed procedure is compared to optimal solutions generated by an exact cutting plane algorithm and upper and lower bounds from the literature. For medium and larger size instances, we developed simple multi-start heuristics and comparative results are reported.