Minimizing job completion time variance for service stability on identical parallel machines

This paper addresses a job scheduling problem on multiple identical parallel machines so as to minimize job completion time variance (CTV). CTV minimization is closely related to the Just-In-Time philosophy and the service stability concept since it penalizes both earliness and tardiness. Its applications can be found in many real-life areas such as Internet data packet dispatching and production planning. This paper focuses on the unrestricted case of the problem where idle times are allowed to exist before machines start to process jobs. We prove several dominant properties about the optimal solution to the problem. For instance, we prove that the mean completion time (MCT) on each machine should be the same under an optimal schedule. Based on these properties, an efficient heuristic algorithm is proposed. Computational experiments are conducted to test the performance of the proposed algorithm. The outputs demonstrate that the proposed algorithm is near optimal for small problem instances and greatly outperforms some existing algorithms for large problem instances.     

Scheduling trees with large communication delays on two identical processors

We consider the problem of scheduling trees on two identical processors in order to minimize the makespan. We assume that tasks have unit execution times, and arcs are associated with large identical integer communication delays. We prove that the problem is NP-hard in the strong sense even when restricted to the class of binary trees, and we provide a polynomial-time algorithm for complete binary trees.This work has been partially supported by the French-Greek bilateral exchange program PLATON and the GDR-PRS Ordonnancement pour le parallélisme program of the French government.     

Minimizing mean weighted execution time loss on identical and uniform processors

The problem of minimizing mean weighted execution time loss was formulated by the present author in 1984; there the preemptive case for identical as well as for a fixed number of uniform processors was solved via a linear programming approach. In this paper, we propose a strongly polynomial algorithm based on a network flow technique, which minimizes the above criterion for an arbitrary number of identical as well as uniform processors. The upper bounds on the number of preemptions in both cases are also given.     

An improved heuristic for minimizing makespan among m identical parallel processors

A simple heuristic for minimizing makespan among identical processors assigned independent tasks is presented and explored. The heuristic initially assigns jobs to processors by applying a quick and effective algorithm which at present is commonly applied to this problem. The heuristic then seeks to identify pairs of jobs that may be interchanged between processors to improve the solution. The conditions under which an optimal makespan may be achieved by such an interchange are derived for the case of two processors. The procedure is then extended to three or more processors. Results of 700 randomly generated problems are reported. The heuristic achieved an optimal solution for most of the problems. The worst case performance for the heuristic has not been established; however, evidence is presented that the worst case for the heuristic is considerably smaller than that of algorithms presently used.     

Completion time variance minimization in single machine and multi-machine systems

In this paper we consider the problem of minimizing the completion time variance of n jobs on a single machine with deterministic processing times. We propose a new heuristic and compare the results with existing popular heuristics for the problem. We also propose a method based on genetic algorithms to solve the problem. We present the worst case performance analysis of the proposed heuristic. We also consider the problem of minimizing the completion time variance of n jobs on m identical parallel machines in both restricted and unrestricted versions. A heuristic method and a method based on genetic algorithms are presented for both the cases and results of computational testing are provided. It is concluded that the proposed methods provide better results compared to existing methods for the single machine case as well as for the multi-machine case.     

Performance considerations in the parallel execution of numerical algorithms on two processors

Summary Loosely coupled multiprocessor systems seem to offer an interesting alternative to the solution of large numerical problems. It is in the context of such an investigation that we treat here a special parallel-processing case concerning the solution of a numerical problem on two independent processors including simultaneous input-output operations. We present a short discussion of the underlying numerical algorithm, a modelling approach to the parallel computing system and a comparison of the theoretically obtained results with simulation and experimental results. The experimental setting is the XANTHOS multi-microprocessor system implemented at the Laboratoire de Recherche en Informatique, Université de Paris-Sud.This work was supported by a DGRST Research Scholarship at Université Paris-Sud     

Minimizing makespan subject to minimum flowtime on two identical parallel machines

We consider the problem of scheduling jobs on two parallel identical machines where an optimal schedule is defined as one that gives the smallest makespan (the completion time of the last job) among the set of schedules with optimal total flowtime (the sum of the completion times of all jobs). We propose an algorithm to determine optimal schedules for the problem, and describe a modified multifit algorithm to find an approximate solution to the problem in polynomial computational time. Results of a computational study to compare the performance of the proposed algorithms with a known heuristic shows that the proposed heuristic and optimization algorithms are quite effective and efficient in solving the problem.Scope and purposeMultiple objective optimization problems are quite common in practice. However, while solving scheduling problems, optimization algorithms often consider only a single objective function. Consideration of multiple objectives makes even the simplest multi-machine scheduling problems NP-hard. Therefore, enumerative optimization techniques and heuristic solution procedures are required to solve multi-objective scheduling problems. This paper illustrates the development of an optimization algorithm and polynomially bounded heuristic solution procedures for the scheduling jobs on two identical parallel machines to hierarchically minimize the makespan subject to the optimality of the total flowtime.     

Automatic test pattern generation on parallel processors

Test generation for combinational circuits is an important step in the VLSI design process. Unfortunately, the problem is highly computation-intensive and for circuits encountered in practice, test generation time can often be enormous. In this paper, we present a parallel formulation of the backtrack search algorithm called PODEM, which is a highly used algorithm for this problem. It is known that the sequential PODEM algorithm consumes most of its execution time in generating tests for ‘hard-to-detect’ (HTD) faults and is often unable to detect them even after a large number of backtracks. Our parallel formulation overcomes these limitations by dividing the search space and searching it concurrently using multiple processes.

We present a number of experimental results and show that these match our theoretical results presented elsewhere. We show that the search efficiency of the parallel algorithm improves and even beats that of the sequential algorithm as the ‘hardness’ of a fault increases. We present speedup results and performance analyses of our formulation on a 128 processor Symult s2010 multicomputer. We also present preliminary results on a network of Sun workstations. Our results show that parallel search techniques provides good speedups as well as high fault coverage of the HTD faults in reasonable time when compared to the uniprocessor implementation. Our experimental validation of most of our theoretical results builds confidence in the following theoretical prediction: our parallel formulation of PODEM is highly scalable on a variety of commercially-available, large MIMD parallel processors (in additions to the ones with which we experimented).     

Lattice gases and parallel processors

This paper introduces the notion of lattice gas as a new medium to perform fluid dymanics simulations. After giving the definition of lattice gases, the results of statistical analyses of their macroscopic behaviour are reviewed. It is shown that Navier-Stokes equations can be simulated. Some information is given concerning the algorithms and their possible adaptation to parallel hard-ware, including cellular automata. Finally the construction of a specialized machine for lattice gas simulations will be presented.     

Analysis and optimum performance of two message-passing parallel processors synchronized by rollback

We analyze a probabilistic model of two processors sharing a common task, such as distributed simulation, proceeding at possibly different rates and with each allowed its own clock and ‘virtual time’. When the task requires it, the processors communicate by messages which are stamped with the local time at the point of origination. This feature is also used to synchronize the processors by ‘rollback’, in which technique a processor receiving a message in its past is required to set its clock and state back as necessary to guarantee correctness. The probabilistic model incorporates for each processor: (i) a distribution for the amount by which the local clock is incremented at each state transition, and (ii) a probability indicating the likelihood of generating a message at each state transition.For the case of exponential distributions we obtain by the method of Wiener-Hopf factorization explicit formulas for the steady-state distribution of the difference in virtual times, the average rate of progress and the average amount of rollback per state transition. We introduce a performance measure which reflects both the average rate of progress and the cost of implementing rollback. This performance measure is optimized with respect to the system parameters and an explicit solution is obtained. This result provides remarkably explicit insights into optimal operations.     

Minimizing total weighted flowtime subject to minimum makespan on two identical parallel machines

We study the problem of scheduling n jobs on two identical parallel processors or machines where an optimal schedule is defined as one with the shortest total weighted flowtime (i.e., the sum of the weighted completion time of all jobs), among the set of schedules with minimum makespan (i.e., the completion time of the last job finished). We present a two phase non-linear Integer Programming formulation for its solution, admittedly not to be practical or useful in most cases, but theoretically interesting since it models the problem. Thus, as an alternative, we propose an optimization algorithm, for small problems, and a heuristic, for large problems, to find optimal or near optimal solutions. Furthermore, we perform a computational study to evaluate and compare the effectiveness of the two proposed methods.     

Optimal quantization of periodic task requests on multiple identical processors

We simplify the periodic tasks scheduling problem by making a trade off between processor load and computational complexity. A set N of periodic tasks, each characterized by its density /spl rho//sub i/, contains n possibly unique values of /spl rho//sub i/. We transform N through a process called quantization, in which each /spl rho/i /spl isin/ N is mapped onto a service level s/sub j/ /spl isin/ L, where |L| = l /spl Lt/ n and /spl rho//sub i/ /spl les/ s/sub j/, (this second condition differentiates this problem from the p-median problem on the real line). We define the periodic task quantization problem with deterministic input (PTQ-D) and present an optimal polynomial time dynamic programming solution. We also introduce the problem PTQ-S (with stochastic input) and present an optimal solution. We examine, in a simulation study, the trade off penalty of excess processor load needed to service the set of quantized tasks over the original set, and find that, through quantization onto as few as 15 or 20 service levels, no more than 5 percent processor load is required above the amount requested. Finally, we demonstrate that the scheduling of a set of periodic tasks is greatly simplified through quantization and we present a fast online algorithm that schedules quantized periodic tasks.     

Scheduling jobs with equal processing times and time windows on identical parallel machines

We present a linear programming approach to the problem of scheduling equal processing time jobs with release dates and deadlines on identical parallel machines. The known algorithm with complexity O(n ³log log n) of B. Simons schedules all the jobs while minimizing both the maximum completion time and the mean flow time. Our approach permits also to minimize the weighted sum of completion times and total tardiness in polynomial time for the problems without deadlines. The complexity status of these problems was open. Contract/grant sponsor: Alexander von Humboldt Foundation.     

Necessary and sufficient optimality conditions for scheduling unit time jobs on identical parallel machines

In this paper we characterize optimal schedules for scheduling problems with parallel machines and unit processing times by providing necessary and sufficient conditions of optimality. We show that the optimality conditions for parallel machine scheduling are equivalent to detecting negative cycles in a specially defined graph. For a range of the objective functions, we give an insight into the underlying structure of the graph and specify the simplest types of cycles involved in the optimality conditions. Using our results we demonstrate that the optimality check can be performed by faster algorithms in comparison with existing approaches based on sufficient conditions.     

Scheduling on parallel processors with varying processing times

In this paper, we construct the pseudopolynomial dynamic programming algorithm that optimally solves the parallel identical processor scheduling problem to minimize the maximum job completion times (makespan) under varying processing times. They can be described by an arbitrary monotonic function dependent on the number of previously processed jobs, which can model learning or aging effects. Beside the canonical dynamic programming algorithm, we provide its efficient parallel fast version, which solves moderate problem instances of the problem within reasonable time and memory usage. Additionally, on the basis of the constructed algorithm, a fully polynomial time approximation scheme for the considered problem is provided.