Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems

This research compares the performance of various heuristics and one metaheuristic for unrelated parallel machine scheduling problems. The objective functions to be minimized are makespan, total weighted completion time, and total weighted tardiness. We use the least significant difference (LSD) test to identify robust heuristics that perform significantly better than others for a variety of parallel machine environments with these three performance measures. Computational results show that the proposed metaheuristic outperforms other existing heuristics for each of the three objectives when run with a parameter setting appropriate for the objective.     

Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective

This paper presents several search heuristics and their performance in batch scheduling of parallel, unrelated machines. Identical or similar jobs are typically processed in batches in order to decrease setup times and/or processing times. The problem accounts for allotting batched work parts into unrelated parallel machines, where each batch consists of a fixed number of jobs. Some batches may contain different jobs but all jobs within each batch should have an identical processing time and a common due date. Processing time of each job of a batch is determined according to the machine group as well as the batch group to which the job belongs. Major or minor setup times are required between two subsequent batches depending on batch sequence but are independent of machines. The objective of our study is to minimize the total weighted tardiness for the unrelated parallel machine scheduling. Four search heuristics are proposed to address the problem, namely (1) the earliest weighted due date, (2) the shortest weighted processing time, (3) the two-level batch scheduling heuristic, and (4) the simulated annealing method. These proposed local search heuristics are tested through computational experiments with data from dicing operations of a compound semiconductor manufacturing facility.     

基于递阶遗传算法的并行多机调度优化

针对最小化完工时间的等同和非等同并行多机调度一类问题，提出了一种递阶遗传算法。该算法根据问题的特点，采用一种递阶编码方案，此编码与调度方案一一对应。用递阶遗传算法优化并行多机调度不需设计专门的遗传算子，操作简单。计算结果表明，递阶遗传算法是有效的，能适用于大规模等同和非等同并行多机调度问题。     

A realistic variant of bi-objective unrelated parallel machine scheduling problem: NSGA-II and MOACO approaches

The problem investigated in this study involves an unrelated parallel machine scheduling problem with sequence-dependent setup times, different release dates, machine eligibility and precedence constraints. This problem has been inspired from a realistic scheduling problem in the shipyard. The optimization criteria are to simultaneously minimize mean weighted flow time and mean weighted tardiness. To formulate this complicated problem, a new mixed-integer programming model is presented. Considering the NP-complete characteristic of this problem, two famous meta-heuristics including a non-dominated sorting genetic algorithm (NSGA-II) and a multi-objective ant colony optimization (MOACO) which is a modified and adaptive version of BicriterionAnt algorithm are developed. Obviously, the precedence constraints increase the complexity of the scheduling problem in strong sense in order to generate feasible solutions, especially in parallel machine environment. Therefore a new corrective algorithm is proposed to obtain the feasibility in all stages of the algorithms. Due to the fact that appropriate design of parameter has a significant effect on the performance of algorithms, we calibrate the parameters of these algorithms by using new approach of Taguchi method. The performances of the proposed meta-heuristics are evaluated by a number of numerical examples. The results indicated that the suggested MOACO statistically outperformed the proposed NSGA-II in solving the test problems. In addition, the application of the proposed algorithms is justified by a real block erection scheduling problem in the shipyard.     

多处理器系统的在线节能调度算法

随着多处理器系统计算性能的提高,能耗管理已变得越来越重要,如何满足实时约束并有效降低能耗成为实时调度中的一个重要问题。基于多处理器计算系统,针对随机到达的任务,提出一种在线节能调度算法(OLEAS)。该算法在满足任务截止期限的前提下,尽量将任务调度到产生能耗最少的处理器,当某个任务在所有处理器上都不能满足截止期限要求时,则调整处理器之间的部分任务,使之尽量满足截止期限要求。同时,OLEAS尽量使单个处理器上的任务按平均电压/频率执行,以降低能耗,只有当新到任务不满足截止期限要求时,才逐个调高前面任务的电压/频率。模拟实验比较了OLEAS、最早完成时间优先(EFF)、最高电压节能(HVEA)、最低电压节能(LVEA)、贪心最小能耗(MEG)和最小能耗最小完成时间(ME-MC)的性能,结果表明OLEAS在满足任务截止期限和节省能耗方面具有明显的综合优势     

Fast reactive scheduling to minimize tardiness penalty and energy cost under power consumption uncertainties

Motivated by the need to deal with uncertainties in energy optimization of flexible manufacturing systems, this paper considers a dynamic scheduling problem which minimizes the sum of energy cost and tardiness penalty under power consumption uncertainties. An integrated control and scheduling framework is proposed including two modules, namely, an augmented discrete event control (ADEC) and a max-throughput-min-energy reactive scheduling model (MTME). The ADEC is in charge of inhibiting jobs which may lead to deadlocks, and sequencing active jobs and resources. The MTME ensures the fulfillment of the innate constraints and decides the local optimal schedule of active jobs and resources. Our proposed framework is applied to an industrial stamping system with power consumption uncertainties formulated using three different probability distributions. The obtained schedules are compared with three dispatching rules and two rescheduling approaches. Our experiment results verify that MTME outperforms three dispatching rules in terms of deviation from Pareto optimality and reduces interrupted time significantly as compared to rescheduling approaches. In addition, ADEC and MTME are programmed using the same matrix language, providing easy implementation for industrial practitioners.     

信任约束下的网格工作流任务调度算法*

提出了信任约束下的网格工作流任务调度算法。该算法结合直接经验和推荐经验计算资源的信任度,根据任务在候选资源上的执行时间确定关键任务,然后选择满足执行时间和信任综合函数的资源。实验结果表明。该算法不仅缩短了工作流的完成时间,而且提高了调度的成功率。     

Simulation of power consumption of cloud data centers

Energy efficiency of cloud data centers received significant attention recently as data centers often consume significant resources in operation. Most of the existing energy-saving algorithms focus on resource consolidation for energy efficiency. This paper proposes a simulation-driven methodology with the accurate energy model to verify its performance, and introduces a new resource scheduling algorithm Best-Fit-Decreasing-Power (BFDP) to improve the energy efficiency without degrading the QoS of the system. Both the model and the resource algorithm have been extensively simulated and validated, and results showed that they are effective. In fact, the proposed model and algorithm outperforms the existing resource scheduling algorithms especially under light workloads.     

染缸排产建模及滑动时间窗启发式调度算法

针对染缸排产问题约束复杂、任务规模大、排产效率要求高的特点,为了提高问题模型和算法在实际场景中的适用性,建立了染缸排产增量调度模型,提出了滑动时间窗启发式调度（STWS）算法。该算法以最小化延误代价、洗缸成本、染缸切换成本为优化目标,使用启发式调度规则,按照优先级顺序调度产品;对于每个产品的调度,先用动态拼缸算法和拆缸算法进行批次划分,然后调用批次最佳排序算法调度批次。使用某染纱企业车间实际生产数据仿真调度,所提算法可在10 s内完成月度计划的调度。相对于人工排产方式,所提算法提高了排产效率,显著优化了三个目标,在增量调度中洗缸成本和染缸切换成本也有明显优化。实验结果表明所提算法具有很好的调度能力。     

An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem

In this work, we tackle the problem of scheduling a set of jobs on a set of unrelated parallel machines with minimising the total weighted completion times as performance criteria. The iterated greedy metaheuristic generates a sequence of solutions by iterating over a constructive heuristic using destruction and construction phases. In the last few years, iterated greedy has been employed to solve a considerable number of problems. This is because it is based on a very simple principle, it is easy to implement, and it often exhibits an excellent performance. Moreover, scalability for high-dimensional problems becomes an essential requirement for modern optimisation algorithms. This paper proposes an iterated greedy model for the above-mentioned scheduling problem to tackle large-size instances. The benefits of our proposal in comparison to existing metaheuristics proposed in the literature are experimentally shown.     

Multi-objective evolutionary algorithms for energy-aware scheduling on distributed computing systems

The ongoing increase of energy consumption by IT infrastructures forces data center managers to find innovative ways to improve energy efficiency. The latter is also a focal point for different branches of computer science due to its financial, ecological, political, and technical consequences. One of the answers is given by scheduling combined with dynamic voltage scaling technique to optimize the energy consumption. The way of reasoning is based on the link between current semiconductor technologies and energy state management of processors, where sacrificing the performance can save energy.This paper is devoted to investigate and solve the multi-objective precedence constrained application scheduling problem on a distributed computing system, and it has two main aims: the creation of general algorithms to solve the problem and the examination of the problem by means of the thorough analysis of the results returned by the algorithms.The first aim was achieved in two steps: adaptation of state-of-the-art multi-objective evolutionary algorithms by designing new operators and their validation in terms of performance and energy. The second aim was accomplished by performing an extensive number of algorithms executions on a large and diverse benchmark and the further analysis of performance among the proposed algorithms. Finally, the study proves the validity of the proposed method, points out the best-compared multi-objective algorithm schema, and the most important factors for the algorithms performance.     

云环境下超启发式能耗感知调度算法

能耗感知调度的研究对云计算数据中心的可持续发展有着重要意义。能耗感知调度是一个NP难的多目标优化问题,目前云环境下的任务调度算法较少考虑能耗问题,且不能实现对能耗的灵活管理,随机搜索算法是一种解决该问题的有效途径,但其计算开销大,收敛速度慢。将异构云环境下的能耗感知调度问题定义为一个带约束的问题,即在一定的完成时间下优化系统能耗,以实现对能耗的灵活管理。此外,提出了基于在线学习的超启发式算法（OLHH）,该算法结合电压调节技术,在设计了简单高效的启发式策略集的基础上,引进超启发式算法,并采用在线学习的方式跟踪启发式策略的表现,实现对启发式策略的合理管理,从而达到提高算法的收敛性能的目的。模拟实验表明,该算法能够实现系统能耗的灵活管理,且比传统的随机搜索算法有着更好的收敛性能。     

Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints

This paper presents a novel, two-level mixed-integer programming model of scheduling N jobs on M parallel machines that minimizes bi-objectives, namely the number of tardy jobs and the total completion time of all the jobs. The proposed model considers unrelated parallel machines. The jobs have non-identical due dates and ready times, and there are some precedence relations between them. Furthermore, sequence-dependent setup times, which are included in the proposed model, may be different for each machine depending on their characteristics. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time using traditional approaches or optimization tools is extremely difficult. This paper proposes an efficient genetic algorithm (GA) to solve the bi-objective parallel machine scheduling problem. The performance of the presented model and the proposed GA is verified by a number of numerical experiments. The related results show the effectiveness of the proposed model and GA for small and large-sized problems.     

Reactive control of overall power consumption in flexible manufacturing systems scheduling: A Potential Fields model

In recent years, designing “energy-aware manufacturing scheduling and control systems” has become more and more complex due to the increasing volatility and unpredictability of energy availability, supply and cost, and thus requires the integration of highly reactive behavior in control laws. The aim of this paper is to propose a Potential Fields-based flexible manufacturing control system that can dynamically allocate and route products to production resources to minimize the total production time. This control system simultaneously optimizes resource energy consumption by limiting energy wastage through the real-time control of resource states, and by dynamically controlling the overall power consumption taking the limited availability of energy into consideration. The Potential Fields-based control model was proposed in two stages. First, a mechanism was proposed to switch resources on/off reactively depending on the situation of the flexible manufacturing system (FMS) to reduce energy wastage. Second, while minimizing wastage, overall power consumption control was introduced in order to remain under a dynamically determined energy threshold. The effectiveness of the control model was studied in simulation with several scenarios for reducing energy wastage and controlling overall consumption. Experiments were then performed in a real FMS to prove the feasibility of the model. The superiority of the proposition is its high reactivity to manage production in real-time despite unexpected restrictions in the amount of energy available. After providing the limitations of the work, the conclusions and prospects are presented.     

Hadoop下资源匹配最大集作业调度算法

针对目前层级队列作业调度算法中资源占比高的作业执行效率低的问题,提出一种资源匹配最大集算法。该算法分析作业特征,引入完成度、等待时间、优先级、重调度次数为紧迫值因子,优先考虑资源占比高或等待时间长的作业,以改善作业公平性;采用双队列结构在可用资源总量内优先选择高紧迫值作业,在不同资源占比作业集比较中选择作业数最大集,以实现调度平衡。在与最大最小公平(Max-min fairness)算法的实例对比中发现,该算法可降低作业集平均等待时间、提高资源利用率。实验对比结果表明,该算法可将不同资源占比的单一类型作业集执行时间缩短18.73%,其中资源占比高的作业执行时间缩短27.26%;在混合型作业集中对应的执行时间可分别缩短22.36%与30.28%。所提算法能有效减少资源占比高作业的等待,提高作业整体执行效率。     

Reactive and energy-aware scheduling of flexible manufacturing systems using potential fields

This paper presents a reactive scheduling approach for flexible manufacturing systems, which integrates the overall energy consumption of the production. This work is justified by the growing needs of manufacturers for energy-aware control, due to new important environmental criteria, which holds true in the context of high reactivity. It makes production hard to predict. The proposed reactive scheduling model is based on potential fields. In this model, resources that sense the intentions from products are able to switch to standby mode to avoid useless energy consumption and emit fields to attract products. Simulations are provided, featuring three indicators: makespan, overall energy consumption and the number of resource switches. Real experiments were carried out to illustrate the feasibility of the approach on a real system and validate the simulation results.     

一种动态能量感知的节点休眠调度算法

为减小低占空比无线传感器网络（LDC-WSN）中端到端的休眠延迟和均衡能量负载,提出了一种动态能量感知的节点休眠调度算法（DESS）,该算法通过感知节点剩余能量的动态变化,自适应地增加苏醒时隙的次数,用以平衡网络中节点的能量消耗。仿真结果表明,与同类算法的LES和TOSS相比,DESS在休眠延迟以及能源消耗等方面带来明显的性能提升,有效地延长网络的生命周期。     

A comprehensive performance and energy consumption analysis of scheduling alternatives in clusters

In this paper, we conduct an in-depth evaluation of a broad spectrum of scheduling alternatives for clusters. These include the widely used batch scheduling, local scheduling, gang scheduling, most prior communication-driven coscheduling algorithms-Dynamic Coscheduling (DCS), Spin Block (SB), Periodic Boost (PB), and Co-ordinated Coscheduling (CC)-and a newly proposed HYBRID coscheduling algorithm on a 16-node, Myrinet-connected Linux cluster. Performance and energy measurements using several NAS, LLNL and ANL benchmarks on the Linux cluster provide several conclusions. First, although batch scheduling is currently used in most clusters, the blocking-based coscheduling techniques such as SB, CC and HYBRID and the gang scheduling can provide much better performance even in a dedicated cluster platform. Second, in contrast to some of the prior studies, we observe that blocking-based schemes like SB and HYBRID can provide better performance than spin-based techniques like PB on a Linux platform. Third, the proposed HYBRID scheduling provides the best performance-energy behavior and can be implemented on any cluster with little effort. All these results suggest that blocking-based coscheduling techniques are viable candidates to be used in clusters for significant performance-energy benefits.

无线传感器网络节点任务调度与功耗管理算法研究

针对有能量采集系统的无线传感器网络节点异质多核SoC平台,从提高能量利用效率的角度,提出了一种任务调度与功耗管理算法.该算法处理实时有截止时间并有相互依赖关系的任务,任务执行在多个电压可调的处理单元上.通过对节点系统能量采集行为和应用情况进行分析建立了问题模型,并运用运筹学软件LINGO对模型做了求解.利用多组随机输入的任务流图对模型与算法进行了验证,该算法在功耗与时间约束范围内确实能有效提高系统的能量利用效率.     

并行机成组调度问题的启发式算法

研究了优化目标为总拖后/提前时间最小化的并行机成组调度问题,提出了一种三阶段启发式近似求解算法。首先把并行机问题看成单机问题,以最小化总拖后时间为优化目标排列工件的加工次序;然后将工件按第一阶段所求得的次序指派到最先空闲的并行的机器上;最后采用改进的GTW算法对各机器上的工件调度插入适当的空闲时间。计算表明该算法能够在很短的时间内给出大规模调度问题的近似最优解。