多机器总完成时间和makespan近似最优的开放式车间调度方法

研究了多机器开放式车间调度问题,采用离散事件系统调度使makespan最小化和总完成时间最小.给出了在确定处理机器的条件下,不同批次的作业总完成时间最优的排序定理,以及选择机器处理作业的指标优化定理,利用给出的若干定理建立了总完成时间最优的调度方法.作者利用加权总完成时间最优算法来近似求解makespan最小化和总完成时间最优的调度问题.作者也利用论文的理论结果给出了一个三机器开放式车间情况的实际算例.     

一类 Flow Shop 调度问题最优调度区间摄动鲁棒性

调度的鲁棒性是调度应用中的一个重要问题.本文从最优调度不变的角度研究了调度的鲁棒性问题.首先定义了最优调度的区间摄动鲁棒性,即当问题中某些参数在各自的区间上变化时最优调度保持不变的性质.然后对比例FlowShop调度问题(任给一个工件它在各台机器上的加工时间都相同)进行了研究.通过一个引理我们证明了本文的结果,该引理指出了r个参数的大小次序与它们的变化区间的相交关系之间的联系.本文的结果是目标函数为完成时间总和时在加工时间扰动下最优调度具有区间摄动鲁棒性的三个充分必要条件,目标函数为最大拖期时间时及目标函数为拖后工件个数时在加工时间和/或交付期扰动下最优调度具有区间摄动鲁棒性的若干充分条件.这些结果与调度在一个由变化参数构成的超矩形的一些顶点上的最优性有关.文中给出了使用这些结果的例子.     

Performance Bounds on Multiprocessor Scheduling Strategies for Chain Structured Programs

In multiprocessors with static allocation of processes to processors, scheduling can be done locally for each processor. The scheduling strategy may have dramatic effect on the execution time of a parallel program. It is NP-hard to find an optimal schedule, and very little is known on how close the heuristic solutions get. In order to obtain nontrivial performance bounds, this study focuses on a restricted class of parallel programs, viz., chain structured programs. The major result is a theorem stating that if certain program parameters are known the execution time of the optimal schedule can be calculated within a factor of 2, even though the optimal schedule is unknown. Using a previously developed tool, one can extract the necessary parameters from a parallel program. This technique makes it possible to compare the execution time for different scheduling strategies with the optimal case. The technique used for calculating the performance bounds gives important hints on how to design efficient scheduling algorithms for chain structured programs.     

网格计算中费用约束的最优时间调度算法

在网格资源处理速度和资源价格异构的网格环境下,讨论基于用户费用约束的最优时间调度问题,提出一种相应的调度算法,将该任务调度问题转化为线性规划问题,采用单纯形算法获得近似最优解,从而获得费用约束下资源的最优执行时间以及该任务的最小完成时间。仿真结果表明,该算法的性能优于其他同类算法。     

Appointment scheduling algorithm considering routine and urgent patients

This paper derives a solution approach to solve the outpatient appointment schedule problem for given numbers of routine and urgent patients considering a no-show probability to minimize the weighted sum of average patient wait time, physician idle time and overtime. An exact deterministic service time method is proposed to find the optimal schedule. An exponentially distributed service time property is presented to show that the objective function for routine and urgent patients is not multimodular, and consequently a local search algorithm based on multimodulary does not guarantee global optimality. Thus, a heuristic algorithm based on two kinds of shifting policies (HE-TKS) is developed to solve the appointment schedule, which gives a local optimal solution as an upper bound for the optimal schedule. Numerical experiments are conducted to illustrate how the critical factors affect service efficiency of the clinic in practice. It reveals that lower no-show probability, smaller interval lengths, shorter service times, and more urgent patients will benefit both patients and clinics.     

Using recorded values for bounding the minimum completion time inmultiprocessors

The way the processes in a parallel program are scheduled on the processors of a multiprocessor system affects the performance significantly. Finding a schedule of processes to processors which results in minimum completion time is NP-hard. Therefore, one has to resort to heuristic schedules. However, it is often difficult to determine if a specific schedule is close to the optimal case or if it is worthwhile to look for other schedules. Based on information from previous executions of the parallel program, we present a formula for an upper bound on the minimum completion time of the program. The bound is a function of a set of parameters. Some of these parameters are obtained from the previous executions of the program and the others describe the target multiprocessor architecture for which we want to bound the minimum completion time. The bound is optimal when it is based on information from one previous execution. Using these results, we are able to decide if a certain schedule is close to optimal or if it is worthwhile to look for other schedules. This is demonstrated by evaluating the completion time of a specific schedule of a particular program. The proofs used for obtaining the bound are based on program transformations and combinatorial mathematics     

An inventory model for deteriorating items under stock-dependent demand and controllable deterioration rate

In this paper, we formulate a deteriorating inventory model with stock-dependent demand by allowing preservation technology cost as a decision variable in conjunction with replacement policy. Moreover, it is assumed that the shortages are allowed and partially backlogged, depending on the length of the waiting time for the next replenishment. The objective is to find the optimal replenishment and preservation technology investment strategies while maximizing the total profit per unit time. For any given preservation technology cost, we first prove that the optimal replenishment schedule not only exists but is unique. Next, we show that the total profit per unit time is a concave function of preservation technology cost when the replenishment schedule is given. We then provide a simple algorithm to find the optimal preservation technology cost and replenishment schedule for the proposed model. Finally, we use some numerical examples to illustrate the model.     

Polynomial Approach to Optimal One-wafer Cyclic Scheduling of Treelike Hybrid Multi-Cluster Tools via Petri Nets

A treelike hybrid multi-cluster tool is composed of both single-arm and dual-arm cluster tools with a treelike topology. Scheduling such a tool is challenging. For a hybrid treelike multi-cluster tool whose bottleneck individual tool is process-bound, this work aims at finding its optimal one-wafer cyclic schedule. It is modeled with Petri nets such that a onewafer cyclic schedule is parameterized as its robots' waiting time. Based on the model, this work proves the existence of its onewafer cyclic schedule that features with the ease of industrial implementation. Then, computationally efficient algorithms are proposed to find the minimal cycle time and optimal onewafer cyclic schedule. Multi-cluster tool examples are given to illustrate the proposed approach. The use of the found schedules enables industrial multi-cluster tools to operate with their highest productivity.      

Fast techniques for the optimal smoothing of stored video

Work-ahead smoothing is a technique whereby a server, transmitting stored compressed video to a client, utilizes client buffer space to reduce the rate variability of the transmitted stream. The technique requires the server to compute a schedule of transfer under the constraints that the client buffer neither overflows nor underflows. Recent work established an optimal off-line algorithm (which minimizes peak, variance and rate variability of the transmitted stream) under the assumptions of fixed client buffer size, known worst case network jitter, and strict playback of the client video. In this paper, we examine the practical considerations of heterogeneous and dynamically variable client buffer sizes, variable worst case network jitter estimates, and client interactivity. These conditions require on-line computation of the optimal transfer schedule. We focus on techniques for reducing on-line computation time. Specifically, (i) we present an algorithm for precomputing and storing the optimal schedules for all possible client buffer sizes in a compact manner; (ii) we show that it is theoretically possible to precompute and store compactly the optimal schedules for all possible estimates of worst case network jitter; (iii) in the context of playback resumption after client interactivity, we show convergence of the recomputed schedule with the original schedule, implying greatly reduced on-line computation time; and (iv) we propose and empirically evaluate an “approximation scheme” that produces a schedule close to optimal but takes much less computation time.     

Inventory and pricing strategies for deteriorating items with shortages: A discounted cash flow approach

In this article, we consider an infinite horizon, single product economic order quantity where demand and deterioration rate are continuous and differentiable function of price and time, respectively. In addition, we allow for shortages and completely backlogged. The objective is to find the optimal inventory and pricing strategies maximizing the net present value of total profit over the infinite horizon. For any given selling price, we first prove that the optimal replenishment schedule not only exists but is unique. Next, we show that the total profit per unit time is a concave function of price when the replenishment schedule is given. We then provide a simple algorithm to find the optimal selling price and replenishment schedule for the proposed model. Finally, we use a couple of numerical examples to illustrate the algorithm.     

一个新的相关任务调度算法

现已有许多调度算法在某些特定条件下能产生最优调度。Darbha和Agrawal提出的TDS算法能产生最优调度，其最优条件比较苛刻，实用性不强。Park和Choe提出一种扩展调度算法（Extended TDS），虽然其最优条件比TDS算法的约束条件宽松些，但在任务数较多时难以满足，并且形式过于复杂。因此，本文提出一种能产生最优调度的新算法，该算法既考虑合并其它父任务以减少通讯时间，同时尽可能少地合并其它任务，从而尽量减小任务的启动时间。该算法不仅最优条件简单、宽松，而且具有与TDS算法相同的时间复杂度O（v^2）。     

Solving single machine scheduling under disruption with discounted costs by quantum-inspired hybrid heuristics

In this paper we study machine disruption on scheduling problem. We focus on the case where the weighted discounted shortest processing time (WDSPT) rule is optimal for original single machine scheduling problem. After a subset of jobs have finished processing, we learn that the machine would be disrupted for some period of time in the future. Therefore a new schedule is needed considering both original objective and the deviation from the initial schedule. The original objective is measured by the weighted discounted total completion time and the deviation is measured by the variances in jobs’ completion times. According to the characteristics of optimal schedule, we design one hybrid heuristic algorithm, combining the advantages of qubit representation in quantum computing and Non-dominated Sorting Genetic Algorithm (NSGA-II). By analyzing the solutions diversity and proximity to optimal Pareto front on several metrics, we demonstrate that the proposed algorithm is effective for machine disruption management.     

Optimal harvesting strategies for a multi-cycle and multi-pond shrimp operation: A practical network model

In this paper, we introduce a network formulation of the optimal scheduling model for a multi-cycle and multi-pond shrimp operation grounded on the original optimal harvesting theory for a single production unit. The optimal schedule comprises the harvesting and restocking time that maximizes total profit throughout the planning horizon, bounded by the underlying biological and economic conditions. The model takes into account the information such as harvest size distribution, seasonality of price, temperature and weight-dependent growth, and labor force and market demand constraints. We applied the model to an existing shrimp operation in Hawaii with 40 one-acre ponds and generated the optimal schedule for a year that maximizes overall production. The model schedule is found to be able to increase total production by 5% when compared to the schedule generated using an “educated” trial-and-error procedure currently practiced by this operation. Further insights for this multi-cycle and multi-pond scheduling problem were also generated through several alternate simulations. It is found that labor force and market demand constraints are the key factors in scheduling multi-cycle and multi-pond shrimp operations.     

Two processor scheduling with limited preemption

We introduce deterministic task system scheduling with limited preemption—that is, a preempted task can resume execution only on the processor where it originally executed. Two classes of limited preemptive schedules are introduced, corresponding to whether or not unforced idle time is allowed in the schedule. Our main result is to show that, on two processors, these two classes are equivalent with respect to optimal schedule lengths. We use this result to establish a hierarchy of optimal schedule lengths.     

An Approximation Algorithm and Dynamic Programming for Reduction in Heterogeneous Environments

Network of workstation (NOW) is a cost-effective alternative to massively parallel supercomputers. As commercially available off-the-shelf processors become cheaper and faster, it is now possible to build a cluster that provides high computing power within a limited budget. However, a cluster may consist of different types of processors and this heterogeneity complicates the design of efficient collective communication protocols. For example, it is a very hard combinatorial problem to find an optimal reduction schedule for such heterogeneous clusters. Nevertheless, we show that a simple technique called slowest-node-first (SNF) is very effective in designing efficient reduction protocols for heterogeneous clusters. First, we show that SNF is actually a 2-approximation algorithm, which means that an SNF schedule length is always within twice of the optimal schedule length, no matter what kind of cluster is given. In addition, we show that SNF does give the optimal reduction time when the cluster consists of two types of processors, when the ratio of communication speed between them is at least two. When the communication speed ratio is less than two, we develop a dynamic programming technique to find the optimal schedule. Our dynamic programming utilizes the monotone property of the objective function, and can significantly reduce the amount of computation time. Finally, combined with an approximation algorithm for broadcast 2004, we propose an all-reduction algorithm which sends the reduction answer to all processors, with approximation ratio 3.5. We conduct three groups of experiments. First, we show that SNF performs better than the built-in MPI_Reduce in a test cluster. Second, we observe a factor of 93 times saving in computation time to find the optimal schedule, when compared with a naive dynamic programming implementation. Thirdly, we apply the theoretical results to a branch-and-bound search and show that they can reduce the search time of the optimal reduction schedule by a factor of 500, when the cluster has three kinds of processors.     

AcT: Accuracy-aware crawling techniques for cloud-crawler

News aggregation websites collect news from various online sources using crawling techniques and provide a unified view to millions of users. Since, news sources update information frequently; aggregators have to recrawl them from time to time in order to have durable archiving of the news content. The majority of recrawling techniques assume the availability of unlimited resources and zero operating cost. However, in reality, the resources and budget are limited and it is impossible to crawl every news source at every point of time. To the best of our knowledge, none of the existing techniques discuss the crawling strategy that can retrieve the maximum amount of information in a resource/budget constrained environment. In this paper, we present a framework AcT that supports two different accuracy-aware personalized crawling techniques to attain the optimal accuracy level of retrieving the information. Given the crawling frequency as a resource constraint, the first scheme aims to find the optimal schedule that maximizes the accuracy. In the second scheme, we optimize the crawling frequency and the corresponding crawling schedule for a given accuracy level. We propose a supervised technique that monitors each news source for a particular time period and collect the news update patterns. The news update patterns are later analyzed using mixed integer programming to discover the optimal crawling schedule for the first scheme, whereas a greedy strategy is proposed to discover the optimal crawling frequency and crawling schedule for the second scheme. We develop a crawler for 87 news sources and performed a series of experiments to demonstrate the quality and efficiency of our proposed techniques against benchmark strategies.     

非对称网络环境中数据广播的启发式多盘调度算法

在以无线网络为代表的非对称网络环境中,数据广播是一种有效的数据访问方式。针对非均匀的访问概率分布,我们分析了数据广播访问时间的最优值,并提出了一种启发式多盘调度算法（ＨＭＤ）,该算法能够根据给定的数据项访问概率分布,自动生成广播调度。 欠的理论分析和实验结果表明,ＨＭＤ算法是一种高效的数据广播调度算法,具有接近于理论最优值的性能,并且具有良好的可操作性。     

On some optimality conditions and their equivalence in time-dependent inventory models

The paper considers a deterministic, time-and-review-continuous, finite horizon inventory model with general time-dependent demand, holding cost, shortage cost and replenishment rate functions. It gives conditions for the optimal ordering schedule, for a fixed number of replenishments, which reduce the effort for its finding to a simple one-dimensional search. The paper also proves equivalence relationships between the derived optimality conditions and the corresponding ones for special cases of the general model where some of its component functions tend to infinity. It concludes with a discussion concerning the uniqueness of the optimal number of replenishments, and the convergence of the optimal ordering schedule for an infinite time horizon.     

Mathematical programming for the scheduling problem with alternate process plans in FMS

The purpose of this research is to consider the operational scheduling problem and the determination of production routing with alternate process plans simultaneously such that the advantages of routing flexibility are expected. The problem is formulated by using 0–1 integer programming regarding to the performance measure of either the minimum of the absolute deviation of meeting due date or the minimum of total completion time. The approach of mathematical programming generates the optimal schedule, rather than near optimal schedule or a better schedule, to meet the selected criterion. Two mathematical formulation models developed are presented and an example is shown in this paper referring to the either one of performance criteria.     

Combined task and message scheduling in distributed real-timesystems

The paper presents an algorithm for offline scheduling of communicating tasks with precedence and exclusion constraints in distributed hard real time systems. Tasks are assumed to communicate via message passing based on a time bounded communication paradigm, such as the real time channel (D.D. Kandlur et al., 1994). The algorithm uses a branch-and-bound (B & B) technique to search for a task schedule by minimizing maximum task lateness (defined as the difference between task completion time and task deadline), and exploits the interplay between task and message scheduling to improve the quality of solution. It generates a complete schedule at each vertex in the search tree, and can be made to yield a feasible schedule (found before reaching an optimal solution), or proceed until an optimal task schedule is found. We have conducted an extensive simulation study to evaluate the performance of the proposed algorithm. The algorithm is shown to scale well with respect to system size and degree of intertask interactions. It also offers good performance for workloads with a wide range of CPU utilizations and application concurrency. For larger systems and higher loads, we introduce a greedy heuristic that is faster but has no optimality properties. We have also extended the algorithm to a more general resource-constraint model, thus widening its application domain