具有不精确活动时间的项目调度算法

针对以最小化项目工期为目标的资源受限项目调度问题,提出对不精确活动时间项目调度的求解方法。对现实项目调度中存在的不精确活动时间及模糊资源分配进行分析,在模糊集理论基础上建立了数学模型,提出一种基于蚁群算法的对不精确活动周期下的项目调度问题求解方法。人工蚂蚁的初始节点采用概率优先约束原则选择,以避免单一概率选择可能导致的过快收敛的局限性,提高解的质量;对算法所使用的重要参数的选择进行分析说明,给出计算方法。进行模拟实例并与其它实验结果进行对比,对比结果表明了该算法的有效性和可行性。     

Algorithms for solving minimax scheduling problem

A series of exact and approximate algorithms are developed for the problem of time-optimal scheduling without interruptions and switchings in a multiprocessor system. The efficiency of these algorithms is determined and the comparative analysis is performed.     

Data aggregation for scheduling of resource-intensive computations under uncertainty

A control process for resource-intensive computations in heterogeneous specialized environment is considered. For each task, a concept of computational job required to execute it is introduced. Two interconnected problems—of capability and performance—are studied. A parametric approach to scheduling is proposed that allows for balanced resource allocation while meeting user requirements under uncertainty.     

Jobshop scheduling with imprecise durations: a fuzzy approach

Jobshop scheduling problems are NP-hard problems. The durations in the reality of manufacturing are often imprecise and the imprecision in data is very critical for the scheduling procedures. Therefore, the fuzzy approach, in the framework of the Dempster-Shafer theory, commands attention. The fuzzy numbers are considered as sets of possible probabilistic distributions. After a review of some issues concerning fuzzy numbers, we discuss the determination of a unique optimal solution of the problem and then we cast a meta-heuristic (simulated annealing-SA) to this particular framework for optimization. It should be stressed that the obtained schedule remains feasible for all realizations of the operations durations     

Heuristic algorithms for scheduling iterative task computations ondistributed memory machines

Many partitioned scientific programs can be modeled as iterative executions of computational tasks and represented by iterative task graphs (ITGs). An ITG may or may not have dependence cycles. In this paper, we consider the symbolic scheduling of ITGs on distributed memory architectures with nonzero communication overhead and propose heuristic algorithms for scheduling both cyclic and acyclic ITGs without searching an entire iteration space. Our approach incorporates techniques of software pipelining, graph unfolding, directed acyclic graph (DAG) scheduling, and load balancing. We analyze the asymptotic optimality of the algorithms to show that the derived schedules are competitive to optimal solutions. We also study the sensitivity of scheduling performance on inaccurate weights. Finally, we present experimental results to demonstrate the effectiveness of the optimization techniques     

Algorithms for handling skew in parallel task scheduling

In this paper we consider the problem of scheduling a collection of independent tasks on multiple processors (denote the number of processors by p) so that the maximum completion time is minimized. We present two new algorithms, the LPT-MinHeight (LPTMH) algorithm and the Split-LPT(SLPT) algorithm. Both algorithms are based on the LPT(Largest Processing Time first) algorithm. The worst case imbalance for the LPTMH algorithm never exceeds 1/(e − 1) ≤ 0.582, while the worst case imbalance for the SLPT algorithm is (p − 1)/(p + 1) < 1. The SLPT bound is equal to the bound for a previously published algorithm while the LPTMH bound is the best known so far. Both LPTMH and SLPT take much less running time than competing algorithms. Results of experiments show that the SLPT algorithm performs better on the average than the LPTMH algorithm and as well as other known algorithms.     

A graph model for scheduling processes in systems with parallel computations

Given a resource system of a finite capacity and a set of independent processes, this paper is concerned with the generation of sequences of allocation steps which are deadlock-free and optimal with respect to total completion time. Processes are defined as partially-ordered sets of phases, each being a single or joint request for resources. A priori knowledge of the duration of phases is assumed to be available. The approach followed is that of combining processes together into a new process which correctly embeds the former. Combination is carried out by the addition of ordering relations between the phases of the original processes. Properties of the new graph model used for process representation permit a short-cut procedure to be introduced to obtain the optimal solution in a nonexhausive way.     

Algorithms for scheduling with applications to parallel computing

Scheduling of message passing for synchronous communication is found to be equivalent to colouring the edges of a graph without conflict. The graph edge-colouring problem, which has other applications, is studied. An algorithm which colours the graph with no more than deg + 1 colours, where deg is the degree of the graph, is implemented. The problem of minimising the sum of the largest weight for each colour is also investigated and an algorithm suggested. These algorithms are used to organise the communication as part of a finite element Euler solver. Different communication schemes and their effect on the performance of the flow solver are compared.     

Algorithms for a realistic variant of flowshop scheduling

This paper deals with a realistic variant of flowshop scheduling, namely the hybrid flexible flowshop. A hybrid flowshop mixes the characteristics of regular flowshops and parallel machine problems by considering stages with parallel machines instead of having one single machine per stage. We also investigate the flexible version where stage skipping might occur, i.e., not all stages must be visited by all jobs. Lastly, we also consider job sequence dependent setup times per stage. The optimization criterion considered is makespan minimization. While many approaches for hybrid flowshops have been proposed, hybrid flexible flowshops have been rarely studied. The situation is even worse with the addition of sequence dependent setups. In this study, we propose two advanced algorithms that specifically deal with the flexible and setup characteristics of this problem. The first algorithm is a dynamic dispatching rule heuristic, and the second is an iterated local search metaheuristic. The proposed algorithms are evaluated by comparison against seven other high performing existing algorithms. The statistically sound results support the idea that the proposed algorithms are very competitive for the studied problem.     

Factoring: Algorithms,computations, and computers

This article discusses the computational structure of the most effective methods for factoring integers and the computer architectures—existing and used, proposed, and under construction—which efficiently perform the computations of these various methods. New developments in technology and in pricing of computers are making it possible to build powerful parallel machines, at relatively low cost, which can substantially outperform standard computers on specific types of computations. The intent of this article is to use factoring and computers for factoring to provoke general thought about this matching of computer architectures to algorithms and computations.The author's research at Louisiana State University was supported in part by the National Science Foundation and the National Security Agency under grants NSF DCR 83-115-80 and NSA MDA904-85-H-0006.     

Jitter minimization in scheduling computations in real-time systems

Scheduling algorithms are proposed for a computational process in single-processor real-time systems. Time it takes to execute the tasks is assumed to be known imprecisely and is given by a time interval, which leads to imprecise task timing (jitter).     

Scheduling multiple task graphs with end-to-end deadlines in distributed real-time systems utilizing imprecise computations

In order to meet the inherent need of real-time applications for high quality results within strict timing constraints, the employment of effective scheduling techniques is crucial in distributed real-time systems. In this paper, we evaluate by simulation the performance of strategies for the dynamic scheduling of composite jobs in a homogeneous distributed real-time system. Each job that arrives in the system is a directed acyclic graph of component tasks and has an end-to-end deadline. For each scheduling policy, we provide an alternative version which allows imprecise computations, taking into account the effects of input error on the processing time of the component tasks of a job. The simulation results show that the alternative versions of the algorithms outperform their respective counterparts. To our knowledge, an imprecise computations approach for the dynamic scheduling of multiple task graphs with end-to-end deadlines and input error has never been discussed in the literature before.     

Algorithms of parallel computations for linear algebra problems with irregularly structured matrices

Parallel algorithms for direct methods of analysis and solution of linear algebra problems with sparse symmetric irregularly structured matrices are considered. The performance of such algorithms is investigated. Upper estimates of the speedup and efficiency factors are obtained for a parallel algorithm for triangular decomposition of sparse matrices. Some results of numerical experiments carried out on a MIMD computer are given.     

Algorithms for scheduling jobs on two serial duplicate stations

In automated assembly or production lines, some stations are duplicated due to their long cycle times. Material handling considerations may require these stations to be arranged in series rather than in parallel. Each job needs to be processed on any one of the duplicate stations. This study deals with scheduling of n available jobs on two serial duplicate stations in an automated production line. The performance measures considered are mean flowtime, makespan, and station idle time. After the problem is formulated, two algorithms are developed to determine the optimal schedules with respect to the performance measures.     

Algorithms for the car sequencing and the level scheduling problem

This paper deals with two most important problems arising in sequencing mixed-model assembly lines. One problem is to keep the line's workstations loads as constant as possible (the 'car sequencing problem') while the other is to keep the usage rate of all parts fed into the final assembly as constant as possible (the 'level scheduling problem'). The first problem is a difficult constraint-satisfaction problem while the second requires to optimize a nonlinear objective function. The contribution of this paper is twofold: First, we describe a branching scheme and bounding algorithms for the computation of feasible sequences for the car sequencing problem. Second, we present an algorithm which can optimize a level scheduling objective while taking care of the car sequencing constraints. Computational results are presented which show that feasible sequences can be obtained quickly for large problem instances.     

Algorithms for scheduling real-time tasks with input error andend-to-end deadlines

This paper describes algorithms for scheduling preemptive, imprecise, composite tasks in real-time. Each composite task consists of a chain of component tasks, and each component task is made up of a mandatory part and an optional part. Whenever a component task uses imprecise input, the processing times of its mandatory and optional parts may become larger. The composite tasks are scheduled by a two-level scheduler. At the high level, the composite tasks are scheduled preemptively on one processor, according to an existing algorithm for scheduling simple imprecise tasks. The low-level scheduler then distributes the time budgeted for each composite task across its component tasks so as to minimize the output error of the composite task     

Algorithms for some maximization scheduling problems on a single machine

In this paper, we consider two scheduling problems on a single machine, where a specific objective function has to be maximized in contrast to usual minimization problems. We propose exact algorithms for the single machine problem of maximizing total tardiness 1‖max-ΣT _j and for the problem of maximizing the number of tardy jobs 1‖maxΣU _j . In both cases, it is assumed that the processing of the first job starts at time zero and there is no idle time between the jobs. We show that problem 1‖max-ΣT _j is polynomially solvable. For several special cases of problem 1‖maxΣT _j , we present exact polynomial algorithms. Moreover, we give an exact pseudo-polynomial algorithm for the general case of the latter problem and an alternative exact algorithm.     

A greedy algorithm for combined scheduling of computations and data exchanges in real-time systems

A mathematical statement of the problem of building consistent schedules for executing application programs and exchanging messages for preliminary given sets of applications and messages is described. This problem arises in the design of real-time management information systems (MISs). Various approaches to the design of algorithms for solving this problem are analyzed, a greedy algorithm is proposed and described, and experimental results concerning this algorithm is presented.     

Economic model of scheduling and fair resource sharing in distributed computations

A model for job flow scheduling and fair resource sharing in distributed computing environments is proposed. The model helps one to take into account requirements in the virtual organization imposed by the users on efficiency and job performance quality. With the proposed slot selection algorithms, one can find alternatives optimal with respect to a given criterion for each job in the batch.