A mathematical model and scheduling heuristics for satisfying prioritized data requests in an oversubscribed communication network

Providing up-to-date input to users' applications is an important data management problem for a distributed computing environment, where each data storage location and intermediate node may have specific data available, storage limitations, and communication links available. Sites in the network request data items and each request has an associated deadline and priority. In a military situation, the data staging problem involves positioning data for facilitating a faster access time when it is needed by programs that will aid in decision making. This work concentrates on solving a basic version of the data staging problem in which all parameter values for the communication system and the data request information represent the best known information collected so far and stay fixed throughout the scheduling process. The network is assumed to be oversubscribed and not all requests for data items can be satisfied. A mathematical model for the basic data staging problem is introduced. Then, three multiple-source shortest-path algorithm-based heuristics for finding a near-optimal schedule of the communication steps for staging the data are presented. Each heuristic can be used with each of four cost criteria developed. Thus, 12 implementations are examined. In addition, two different weightings for the relative importance of different priority levels are considered. The performance of the proposed heuristics are evaluated and compared by simulations. The proposed heuristics are shown to perform well with respect to upper and lower bounds. Furthermore, the heuristics and a complex cost criterion allow more highest priority messages to be received than a simple-cost-based heuristic that schedules all highest priority messages first.     

A path selection-based algorithm for real-time data staging in Grid applications

Efficient data scheduling is becoming an important issue in distributed real-time applications that produce huge data sets. The Grid environment on which these applications may run seeks to harness the geographically distributed resources for the applications. Scheduling components should account for real-time measures of the applications and reduce communication overhead due to enormous data size experienced, especially in dissemination applications. In this study, we consider the data staging scheme to provide the dissemination of large-scale data sets for the distributed real-time applications. We propose a new path selection-based algorithm for optimizing a criterion that reflects the general satisfiability of the system. The algorithm adopts a blocking-time analysis method combined with a simple heuristic to explore the most likely regions of a search space. Two heuristics are provided for the algorithm to explore these regions of the search space. Simulation results show that the proposed algorithm together with either of the heuristic has higher performance compared to other algorithms in the literature. We also show by simulation that a new optimization criterion we proposed in this study is successful in improving the performance of the individual applications.     

Three insertion heuristics and a justification improvement heuristic for two-dimensional bin packing with guillotine cuts

The problem of packing two-dimensional items into two-dimensional bins is considered in which patterns of items allocated to bins must be guillotine-cuttable and item rotation might be allowed (2BP|?|G)$(2\mathrm{BP}|?|\mathrm{G})$. Three new constructive heuristics, namely, first-fit insertion heuristic, best-fit insertion heuristic, and critical-fit insertion heuristic, and a new justification improvement heuristic are proposed. All new heuristics use tree structures to represent guillotine-cuttable patterns of items and proceed by inserting one item at a time in a partial solution. Central to all heuristics are a new procedure for enumerating possible insertions and a new fitness criterion for choosing the best insertion. All new heuristics have quadratic worst-case computational complexity except for the critical-fit insertion heuristic which has a cubic worst-case computational complexity. The efficiency and effectiveness of the proposed heuristics is demonstrated by comparing their empirical performance on a standard benchmark data set against other published approaches.     

Learning Heuristics for the Superblock Instruction Scheduling Problem

Modern processors have multiple pipelined functional units and can issue more than one instruction per clock cycle. This places a burden on the compiler to schedule the instructions to take maximum advantage of the underlying hardware. Superblocks—a straight-line sequence of code with a single entry point and multiple possible exit points—are a commonly used scheduling region within compilers. Superblock scheduling is NP-complete, and is done suboptimally in production compilers using a greedy algorithm coupled with a heuristic. The heuristic is usually handcrafted, a potentially time-consuming process. In this paper, we show that supervised machine learning techniques can be used to semiautomate the construction of heuristics for superblock scheduling. In our approach, labeled training data were produced using an optimal superblock scheduler. A decision tree learning algorithm was then used to induce a heuristic from the training data. The automatically constructed decision tree heuristic was compared against the best previously proposed, handcrafted heuristics for superblock scheduling on the SPEC 2000 and MediaBench benchmark suites. On these benchmark suites, the decision tree heuristic reduced the number of superblocks that were not optimally scheduled by up to 38 percent, and led to improved performance on some architectural models and competitive performance on others.     

Real time stochastic scheduling in broadcast systems with decentralized data storage

Data broadcasting is an efficient method to disseminate information to a large group of requesters with common interests. Performing such broadcasts typically involve the determination of a broadcast schedule intended to maximize the quality of service provided by the broadcast system. Earlier studies have proposed solutions to this problem in the form of heuristics and local search techniques designed to achieve minimal deadline misses or maximal utility. An often ignored factor in these studies is the possibility of the data items being not available locally, but rather have to be fetched from data servers distributed over a network, thereby inducing a certain level of stochasticity in the actual time required to serve a data item. This stochasticity is introduced on behalf of the data servers which themselves undergo a dynamic management of serving data requests. In this paper we revisit the problem of real time data broadcasting under such a scenario. We investigate the efficiency of heuristics that embed the stochastic nature of the problem in their design and compare their performance with those proposed for non-stochastic broadcast scheduling. Further, we extend our analysis to understand the various factors in the problem structure that influence these heuristics, and are often exploited by a better performing one.     

Efficient constructive and composite heuristics for the Permutation Flowshop to minimise total earliness and tardiness

In this paper we address the problem of scheduling jobs in a permutation flowshop with a just-in-time objective, i.e. the minimisation of the sum of total tardiness and total earliness. Since the problem is NP-hard, there are several approximate procedures available for the problem, although their performance largely depends on the due dates of the specific instance to be solved. After an in-depth analysis of the problem, different cases or sub-problems are identified and, by incorporating this knowledge, four heuristics are proposed: a fast constructive heuristic, and three different local search procedures that use the proposed constructive heuristic as initial solution.The proposed Prod. Type: FLPheuristics have been compared on an extensive set of instances with the best-so-far heuristic for the problem, as well as with adaptations of efficient heuristics for similar scheduling problems. The computational results show the excellent performance of the proposed algorithms. Finally, the positive impact of the efficient heuristics is evaluated by including them as seed sequences for one of the best metaheuristic for the problem.     

MRP rescheduling heuristics with capacity extension under deterministic demand

The multi-stage, multi-machine capacitated lot-sizing problem (MSMMCLSP) consists of scheduling the production of one product in a multi-machine production system with a multi-stage structure. Machine capacity is reserved for the production of the end item but can be extended by working overtime (overtime capacity). When a lot size is positive in a specific period, it can be loaded on all machines without exceeding the sum of the regular and overtime capacity limits. In previous research [Rong, C., Takahashi, K., & Morikawa, K. (2005). A new heuristic method for capacitated lot-sizing in multi-stage, multi-machine production systems. Journal of Japan Industrial Management Association, 56(5), in press], we have proposed a rescheduling heuristic to determine a feasible and sufficient solution for the MSMMCLSP with only regular capacity limits, in comparison with Franca et al.’s heuristic method. However, the mechanism of rescheduling in regular time has not optimum (or near optimum) performance for the MSMMCLSP with capacity extension. Preliminary examination revealed that overtime production also has situation-dependent advantages and disadvantages with the combination of various planning parameters. This study, therefore, develops an integrated heuristic that guarantees an optimal solution for general MSMMCLSP by combining the rescheduling mechanism and overtime production. We also evaluate the effectiveness of the proposed heuristics by using computational tests with various planning parameters.     

一种基于虚拟截止时间制导的改进的Min-Min元任务调度算法

在网格环境下,资源状况和用户行为相当复杂,是一个异构计算环境,元任务（meta—task）调度比传统并行调度更为复杂。如何映射一组任务到一组机器上被证明是NP问题,其目的一般是最小化任务完成时间（makespan）。为解决这一问题,已经提出一些启发式任务调度算法,例如具有代表性的MinMin元任务调度算法。本文在Min-Min元任务调度算法的基础上,通过虚拟截止时间制导的方法来改进Min-Min算法。实验结果表明,本文提出的算法具有更短的任务完成时间。     

A meta-heuristic approach to solve a JIT scheduling problem in hybrid flow shop

In this paper we address a hybrid flow shop scheduling problem considering the minimization of the sum of the total earliness and tardiness penalties. This problem is proven to be NP-hard, and consequently the development of heuristic and meta-heuristic approaches to solve it is well justified. So, we propose an ant colony optimization method to deal with this problem. Our proposed method has several features, including some heuristics that specifically take into account both earliness and tardiness penalties to compute the heuristic information values. The performance of our algorithm is tested by numerical experiments on a large number of randomly generated problems. A comparison with solutions performance obtained by some constructive heuristics is presented. The results show that the proposed approach performs well for this problem.     

Experimental evaluation of various register‐pressure‐reduction heuristics

Minimizing the amount of spill code is still an open problem in code generation and optimization. The amount of spill code depends on both the register allocation algorithm and the pre‐allocation instruction scheduling algorithm that controls the register pressure. In this paper, we focus on the impact of pre‐allocation instruction scheduling on the amount of spill code. Many heuristic techniques have been proposed to do instruction scheduling with the objective of minimizing register pressure and consequently the amount of spill code. However, the performance of these heuristic techniques has not been studied relative to optimality on real large‐scale programs. In this paper, we present an experimental study that evaluates the performance of several pre‐allocation scheduling heuristics. The evaluation involves computing an experimental lower bound on the size of gap between each heuristic's performance and optimal performance. We also propose a simple heuristic technique based on a specific permutation of two basic priority schemes and experimentally evaluate the performance of this technique compared with other heuristics, including the heuristics implemented in the LLVM open‐source Compiler. The evaluation is carried out by running SPEC CPU2006 on real x86‐64 hardware and measuring both the amount of spill code and the execution time. The results of our study show that the proposed heuristic technique gives better overall performance than LLVM's best heuristic on x86‐64, although it produces slightly more spilling. The proposed heuristic has better overall performance, because it achieves a better balance between register pressure and instruction‐level parallelism (ILP). This result shows the importance of ILP in pre‐allocation scheduling even on out‐of‐order machines. Furthermore, the results of the study show that there is a large gap between the performance of any of the studied heuristics and optimal performance; even the best heuristic in the study produces significantly more spill code than the optimal amount. This experimental result quantifies the intuitive belief that it is unlikely to find a heuristic that works well in all cases, thus showing the need for more rigorous solutions using combinatorial approaches. The paper discusses the challenges and complexities that are involved in developing such rigorous solutions. Copyright © 2014 John Wiley & Sons, Ltd.     

Single machine scheduling problem with interval processing times to minimize mean weighted completion time

The single resource scheduling problem is commonly applicable in practice not only when there is a single resource but also in some multiple-resource production systems where only one of the resources is bottle neck. Thus, the single resource (machine) scheduling problem has been widely addressed in the scheduling literature. In this paper, the single machine scheduling problem with uncertain and interval processing times is addressed. The objective is to minimize mean weighted completion time. The problem has been addressed in the literature and efficient heuristics have been presented. In this paper, some new polynomial time heuristics, utilizing the bounds of processing times, are proposed. The proposed and existing heuristics are compared by extensive computational experiments. The conducted experiments include a generalized simulation environment and several additional representative distributions in addition to the restricted experiments used in the literature. The results indicate that the proposed heuristics perform significantly better than the existing heuristics. Specifically, the best performing proposed heuristic reduces the error of the best existing heuristic in the literature by more than 75% while the computational time of the best performing proposed heuristic is less than that of the best existing heuristic. Moreover, the absolute error of the best performing heuristic is only about 1% of the optimal solution. Having a very small absolute error along with a negligible computational time indicates the superiority of the proposed heuristics.     

Hybrid greedy heuristics based on linear programming for the three‐dimensional single bin‐size bin packing problem

In this paper, we propose to solve the three‐dimensional single bin‐size bin packing problem (3D‐SBSBPP) using a simple strategy based on integer linear programming (ILP) heuristics, without using any improvement based on metaheuristics. We first propose an ILP that is converted into a series of three‐dimensional single knapsack problems (3D‐SKP). Then, the first tailored heuristic can be viewed as a hybrid approach in which both “selection” and “positioning” phases are combined. The first phase serves to select a subset of items where each of these items is susceptible to belonging to an active container. The positioning phase serves to pack a subset of items already preselected by the selection phase. Then, both phases cooperate till packing all items into their corresponding containers. The second heuristic can be viewed as an extended version of the first one. Indeed, before deciding whether the current container is closed or a new container is activated, “a local reoptimization phase” is considered. Finally, both proposed heuristics are evaluated on a set of random instances obtained by using the standard generator scheme of the literature. The provided results show that both proposed heuristics remain competitive when compared to the results obtained by one of the best methods of the literature.     

Dispatching heuristics for the single machine early/tardy scheduling problem with job-independent penalties

In this paper, we consider the single machine earliness/tardiness scheduling problem with job-independent penalties, and no machine idle time. Several dispatching heuristics are proposed, and their performance is analysed on a wide range of instances. The heuristics include simple scheduling rules, as well as a procedure that takes advantage of the strengths of each of those rules. We also consider early/tardy dispatching procedures, and a heuristic method based on existing adjacent precedence conditions. An improvement procedure that can be used to improve the schedules generated by the heuristics is also proposed.

The computational tests show that the best results are given by the early/tardy dispatching rules. These heuristics are also quite fast, and are capable of quickly solving even very large instances. The use of the improvement procedure is recommended, since it improves the solution quality, with little additional computational effort.     

Conditions for On-line Scheduling of Hard Real-Time Tasks on Multiprocessors

In this paper we consider the problem ofon-linescheduling ofhard real-timetasks onmultipleprocessors. For a given set of ready tasks, one can propose many schedules. These schedules, however, may not necessarily be suitable for on-line scheduling. A suitable on-line schedule is one which can accommodate any future task set when it arrives. The traditional approach to solve the on-line scheduling problem is to propose a heuristic, and then to prove its effectiveness by comparing it with existing heuristics using simulation. No attempt has, however, been made to obtain a condition on the current schedule which when satisfied will permit one to schedule an arbitrary future task. In this paper, we aim at developing such a condition on the current schedule for the set of ready tasks which when satisfied can guarantee an on-line schedule for any futurefeasibletask set.     

A hybrid data mining heuristic to solve the point‐feature cartographic label placement problem

A clean map visualization requires the fewest possible overlaps and depends on how labels are attached to point features. In this paper, we address the cartographic label placement variant problem whose objective is to label a set of points maximizing the number of conflict‐free points. Thus, we propose a hybrid data mining heuristic to solve the point‐feature cartographic label placement problem based on a clustering search (CS) heuristic, a state‐of‐the‐art method for this problem. Although several works have investigated the combination of data mining and multistart metaheuristics, this is the first time data mining has been used to improve CS and simulated annealing based heuristics. Computational experiments showed that the proposed hybrid heuristic was able to reach better cost solutions than the original strategy, with the same time effort. The proposed heuristic also could find almost all known optimal solutions and improved most of the best results for the set of large instances reported so far in the literature.     

A note on a single-machine lot scheduling problem with indivisible orders

In this paper, a lot scheduling problem on a single machine with indivisible orders is studied. The objective is to minimize the total completion time of all orders. We show that the problem is NP-hard in the strong sense. Then, a binary integer programming approach and four simple heuristics are proposed to solve the problem. The binary integer programming approach with running time limit is considered as one heuristic method. As compared to a lower bound, the average performances of the heuristic method are really good and better than those of the four simple heuristics.     

A computational study of heuristic and exact techniques for superblock instruction scheduling

Compilers perform instruction scheduling to improve the performance of code on modern computer architectures. Superblocks??a straight-line sequence of code with a single entry point and multiple possible exit points??are a commonly used scheduling region within compilers. Superblock scheduling is NP-complete, and is done suboptimally in production compilers using a greedy algorithm coupled with a heuristic. Recently, exact schedulers have also been proposed. In this paper, we perform an extensive computational study of heuristic and exact techniques for scheduling superblocks. Our study extends previous work in using a more realistic architectural model, in not assuming perfect profile information, and in systematically investigating the case where profile information is not available. Our experimental results show that heuristics can be brittle and what looks promising under idealized (but unrealistic) conditions may not be robust in practice. As well, for the case where profile information is not available, some methods clearly dominate. Notably, a much inferior method is deployed in at least one existing compiler.     

A beam-search-based constructive heuristic for the PFSP to minimise total flowtime

In this paper we present a beam-search-based constructive heuristic to solve the permutation flowshop scheduling problem with total flowtime minimisation as objective. This well-known problem is NP-hard, and several heuristics have been developed in the literature. The proposed algorithm is inspired in the logic of the beam search, although it remains a fast constructive heuristic.The results obtained by the proposed algorithm outperform those obtained by other constructive heuristics in the literature for the problem, thus modifying substantially the state-of-the-art of efficient approximate procedures for the problem. In addition, the proposed algorithm even outperforms two of the best metaheuristics for many instances of the problem, using much lesser computation effort. The excellent performance of the proposal is also proved by the fact that the new heuristic found new best upper bounds for 35 of the 120 instances in Taillard’s benchmark.     

A computational evaluation of constructive and improvement heuristics for the blocking flow shop to minimise total flowtime

This paper focuses on the blocking flow shop scheduling problem with the objective of total flowtime minimisation. This problem assumes that there are no buffers between machines and, due to its application to many manufacturing sectors, it is receiving a growing attention by researchers during the last years. Since the problem is NP-hard, a large number of heuristics have been proposed to provide good solutions with reasonable computational times. In this paper, we conduct a comprehensive evaluation of the available heuristics for the problem and for related problems, resulting in the implementation and testing of a total of 35 heuristics. Furthermore, we propose an efficient constructive heuristic which successfully combines a pool of partial sequences in parallel, using a beam-search-based approach. The computational experiments show the excellent performance of the proposed heuristic as compared to the best-so-far algorithms for the problem, both in terms of quality of the solutions and of computational requirements. In fact, despite being a relative fast constructive heuristic, new best upper bounds have been found for more than 27% of Taillard’s instances.     

Wingrid-面向参数扫描应用的网格计算系统

参数扫描应用在计算网格环境下扮演十分重要的角色。在Wingrid项目中,我们提出并实现了一种面向参数扫描的自适应调度机制。客户端,主节点和从节点的调度基础设施,以及基于领导节点的通信系统能够改善调度的效率。同时,我们比较了自适应workqueue算法和标准启发式调度算法。实验结果显示大网络延迟下,启发式调度算法效率高于workqueue算法,在各种启发式算法中,min-min启发式算法的任务完成时间最小。