Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups

In this paper, we consider the single machine weighted tardiness scheduling problem with sequence-dependent setups. We present heuristic algorithms based on the beam search technique. These algorithms include classic beam search procedures, as well as the filtered and recovering variants. Previous beam search implementations use fixed beam and filter widths. We consider the usual fixed width algorithms, and develop new versions that use variable beam and filter widths.     

Single-machine scheduling with deteriorating jobs under a series–parallel graph constraint

This paper considers single-machine scheduling problems with deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. In addition, the jobs are related by a series–parallel graph. It is shown that for the general linear problem to minimize the makespan, polynomial algorithms exist. It is also shown that for the proportional linear problem of minimization of the total weighted completion time, polynomial algorithms exist, too.     

A genetic algorithm for the Flexible Job-shop Scheduling Problem

In this paper, we present a genetic algorithm for the Flexible Job-shop Scheduling Problem (FJSP). The algorithm integrates different strategies for generating the initial population, selecting the individuals for reproduction and reproducing new individuals. Computational result shows that the integration of more strategies in a genetic framework leads to better results, with respect to other genetic algorithms. Moreover, results are quite comparable to those obtained by the best-known algorithm, based on tabu search. These two results, together with the flexibility of genetic paradigm, prove that genetic algorithms are effective for solving FJSP.     

A new approach to the learning effect: Beyond the learning curve restrictions

In this paper, we bring into the scheduling field a new model of the learning effect, where in two ways the existing approach is generalized. First we relax one of the rigorous constraints, and thus in our model each job can provide different experience to the processor. Second we formulate the job processing time as a non-increasing k-stepwise function, that, in general, is not restricted to a certain learning curve, thereby it can accurately fit every possible shape of a learning function. Furthermore, we prove that the problem of makespan minimization with the considered model is polynomially solvable if every job provides the same experience to the processor, and it becomes NP-hard if the experiences are diversified. The most essential result is a pseudopolynomial time algorithm that solves optimally the makespan minimization problem with any function of an experience-based learning model reduced into the form of the k-stepwise function.     

A two-stage hardware scheduler combining greedy and optimal scheduling

Greedy scheduling heuristics provide a low complexity and scalable albeit particularly sub-optimal strategy for hardware-based crossbar schedulers. In contrast, the maximum matching algorithm for Bipartite graphs can be used to provide optimal scheduling for crossbar-based interconnection networks with a significant complexity and scalability cost. In this paper, we show how maximum matching can be reformulated in terms of Boolean operations rather than the more traditional formulations. By leveraging the inherent parallelism available in custom hardware design, we reformulate maximum matching in terms of Boolean operations rather than matrix computations and introduce three maximum matching implementations in hardware. Specifically, we examine a Pure Logic Scheduler with three dimensions of parallelism, a Matrix Scheduler with two dimensions of parallelism and a Vector Scheduler with one dimension of parallelism. These designs reduce the algorithmic complexity for an N×N$N\times N$ network from O(N³)$O\left(N^3\right)$ to O(1)$O\left(1\right)$, O(K)$O\left(K\right)$, and O(KN)$O\left(KN\right)$, respectively, where K$K$ is the number of optimization steps. While an optimal scheduling algorithm requires K=2N−1$K=2N-1$ steps, by starting with our hardware-based greedy strategy to generate an initial schedule, our simulation results show that the maximum matching scheduler can achieve 99% of the optimal schedule when K=9$K=9$. We examine hardware and time complexity of these architectures for crossbar sizes of up to N=1024$N=1024$. Using FPGA synthesis results, we show that a greedy schedule for crossbars, ranging from 8×8 to 256×256, can be optimized in less than 20 ns per optimization step. For crossbars reaching 1024×1024 the scheduling can be completed in approximately 10 μs with current technology and could reach under 90 ns with future technologies.     

能源管理在湘钢的应用

我国面临着巨大的能源压力。钢铁企业是耗能大户,而我国钢铁企业的能耗高,能耗管理水平与国际同行相比有较大差距。从钢铁企业入手,进行有效的能源生产和调度管理,对于企业的节能减排有着非常好的示范作用。本文介绍了湘钢能源调管理的现状,分析了当前能源改造的难点,提出了湘钢能源调度管理的要求,设计了能源管理方案,并分析了实施后带来的效果。可以作为类似企业的一种能源管理方案的借鉴。     

基于覆盖架构的NCS最小代价调度策略

将覆盖网络引入到基于Internet的网络控制系统（NCS）中,讨论了一种适合于Internet网络控制系统的相近最小代价调度（MLCS）策略,并对其进行了优化。通过仿真系统表明,该基于覆盖网络的调度及其优化策略能有效地保证网络服务质量QoS,从而提高NCS的性能。     

Multicast Pull Scheduling: When Fairness Is Fine

Abstract. We investigate server scheduling policies to minimize average user perceived latency in pull-based client-server systems (systems where multiple clients request data from a server) where the server answers requests on a multicast/ broadcast channel. We first show that there is no O(1) -competitive algorithm for this problem. We then give a method to convert any nonclairvoyant unicast scheduling algorithm A to nonclairvoyant multicast scheduling algorithm B . We show that if A works well, when jobs can have parallel and sequential phases, then B works well if it is given twice the resources. More formally, if A is an s -speed c -approximation unicast algorithm, then its counterpart algorithm B is a 2s -speed c -approximation multicast algorithm. It is already known [5] that Equi-partition, which devotes an equal amount of processing power to each job, is a (2 + ε) -speed O(1 + 1/ε) -approximation algorithm for unicast scheduling of such jobs. Hence, it follows that the algorithm {BEQUI}, which broadcasts all requested files at a rate proportional to the number of outstanding requests for that file, is a (4 + ε) -speed O(1 + 1/ε) -approximation algorithm. We give another algorithm BEQUI-EDF and show that BEQUI-EDF is also a (4 + ε) -speed O(1 + 1/ε) -approximation algorithm. However, BEQUI-EDF has the advantage that the maximum number of preemptions is linear in the number of requests, and the advantage that no preemptions occur if the data items have unit size.     

基于贪婪算法成像侦察卫星调度方法研究

成像侦察卫星的调度问题需要考虑大量互相联系的约束条件,实现全面调度的难度比较大,特别是在作战的情况下,很难满足快速战略决策的要求,而且各种干扰因素将会对卫星的状态产生影响,需要优越的初始调度方案作为基础.针对以上提出的实际问题,首先对成像侦查卫星约束条件进行分析,在简单假设的基础上对问题进行描述,建立卫星调度的约束模型,基于贪婪算法原理,通过软件实现调度模型求解,得到成像侦查卫星的快速调度方案,为卫星任务状态变化的二次调度和满足快速战略决策提供比较令人满意的调度基础解.     

STK/Scheduler在卫星数传调度中的应用研究

卫星数传调度问题是一类复杂的组合优化问题,即如何为卫星数传任务分配地面资源的问题,它是当前航天领域需要重点研究的问题之一.STK/Scheduler模块是STK工具包中的调度模块,对外提供了二次开发功能.针对卫星数传调度问题,研究了STK/Scheduler模块在该问题中的应用.首先在分析问题的基础上建立了卫星数传任务模型和调度模型,然后对基于STK/Scheduler的卫星数传调度系统进行了设计.最后利用AFIT基准数据进行了验证,结果表明在卫星数传任务规模不太大的情况下,TK/Scheduler为卫星数传调度问题的求解提供了一条捷径.