Memory management optimization problems for integrated circuit simulators

In hardware design, it is necessary to simulate the anticipated behavior of the integrated circuit before it is actually cast in silicon. As simulation procedures are long due to the great number of tests to be performed, optimization of the simulation code is of prime importance. This paper describes two mathematical models for the minimization of the memory access times for a cycle-based simulator.An integrated circuit being viewed as a directed acyclic graph, the problem consists in building a graph order on the vertices, compatible with the relation order induced by the graph, in order to minimize a cost function that represents the memory access time. For both proposed cost functions, we show that the corresponding problems are NP-complete. However, we show that the special cases where the graphs are in-trees or out-trees can be solved in polynomial time.     

Influence of the Excited States of Atomic Nitrogen N(<Superscript>2</Superscript>D), N(<Superscript>2</Superscript>P) and N(R) on the Transport Properties of Nitrogen. Part II: Nitrogen Plasma Properties

In this paper, the calculated values of the viscosity and thermal conductivity of nitrogen plasma are presented taking into account five (e, N, N⁺, N₂ and N₂⁺) or eight (e, N(⁴S), N(²P), N(²D), N(R), N⁺, N₂ and N₂⁺) species. The calculations are based on the supposition that the temperature dependent probability of occupation of the states is given by the Boltzmann factor. The domain for which the calculations are performed, is for p = 1 and 10 atm in the temperature range from 5,000 K to 15,000 K. Classical collision integrals are used in calculating the transport coefficients and we have introduced new averaged collision integrals where the weight associated at each interacting species pair is the probable collision frequency. The influence of the collision integral values and energy transfer between two different species is studied. These results are compared which those of published theoretical studies.     

Influence of the Excited States of Atomic Nitrogen N(<Superscript>2</Superscript>D) and N(<Superscript>2</Superscript>P) on the Transport Properties of Nitrogen. Part I: Atomic Nitrogen Properties

In this paper, calculated values of the viscosity and thermal conductivity of atomic nitrogen, taking into account three species (the ground and two excited states), are presented. The calculations, which assume that the temperature dependent probability of occupation of the states is given by the Boltzmann factor, are performed for atmospheric-pressure in the temperature range from 1,000 to 20,000 K. Six collision integrals are used in calculating the transport coefficients and we have introduced new averaged collision integrals where the weight associated at each interacting species pair is the probable collision frequency. The influence of the collision integral values and energy transfer between two different species is studied. These results are compared which those of published theoretical studies.     

Scheduling Tasks on Unrelated Machines: Large Neighborhood Improvement Procedures

Two approximation algorithms are presented for minimizing the makespan of independant tasks assigned on unrelated machines. The first one is based upon a partial and heuristical exploration of a search tree, which is used not only to build a solution but also to improve it thanks to a post-optimization procedure. The second implements a new large neighborhood improvement procedure to an already existing algorithm. Computational experiments show that their efficiency is equivalent to the best local search heuristics.     

On maximizing the profit of a satellite launcher: Selecting and scheduling tasks with time windows and setups

At regular times, a satellite launcher company has to plan the use of its launcher to get the maximum profit. In a more formal way, the problem consists of selecting and scheduling a subset of unit-length jobs constrained by capacitated time slots so that the overall cost is a minimum. The data associated with each job are its weight, its time-window and its expected gain when it is performed. With each time slot are associated a setup cost and a capacity. The setup cost of a time slot is due when this time-slot is used to perform at least one job. Moreover the total weight of all jobs scheduled within a time slot is at most the time slot capacity. We first show that the general problem is hard and provide some easy special cases. We then propose a first dynamic-programming polynomial-time algorithm for the special case with unit weights. A second and more efficient dynamic programming algorithm is also provided for the special case of unit weights and agreeable time windows. This last algorithm is finally improved for the special case of equal gains.     

Single machine scheduling with forbidden start times

This paper addresses a single machine scheduling problem in which the following simple constraint is added: a set of time slots is forbidden for starting a task, that is no task can start at any forbidden time point. We show that the single machine problem with makespan minimization is strongly -complete and we give polynomial algorithms to solve the problems with a small number of forbidden start times.      

Dynasearch for the earliness-tardiness scheduling problem with release dates and setup constraints

A large dynasearch neighborhood is introduced for the one-machine scheduling problem with sequence-dependent setup times and costs and earliness-tardiness penalties. Finding the best schedule in this neighborhood is NP-complete in the ordinary sense but can be done in pseudo-polynomial time. We also present experimental results.     

Preemptive Scheduling with Two Minimax Criteria

Two preemptive single-machine bicriteria scheduling problems with release dates and deadlines are considered in this paper. Each criterion is formulated as a maximum cost. In the first problem the cost of both criteria depends on the completion time of the tasks. This problem can be solved by enumerating all the Pareto optimal points with an approach proposed by Hoogeveen (1996) for the nonpreemptive problem without release dates. In the second problem, the costs of one criterion are dependent on the completion times of the tasks and the costs of the other criterion are dependent on the start times. This problem is more difficult but an efficient algorithm is proposed for a sub-problem with heads, tails, release dates and deadlines that appears in the job-shop scheduling problem.