Modèle mathématique d'ordonnancement de fabrication en série
Monotone interval eigenproblem in max–min algebra
The interval eigenproblem in max-min algebra is studied. A classification of interval eigenvectors is introduced and six types of interval eigenvectors are described. Characterization of all six types is given for the case of strictly increasing eigenvectors and Hasse diagram of relations between the types is presented.
MOPP-I: an optimization package for multipurpose batch operations.
A number of algorithms have been developed -including enumeration of feasible production sequences, alternative task selection and the generation of alternative production lines- to determine the optimal sequence in which products and by-products should be produced and the times at which the various production operations for each product should be carried out to meet a given product demand pattern, taking into account the available equipment, storage costs, stopover penalties and other plant limitations.Product...
New algorithms for coupled tasks scheduling – a survey
The coupled tasks scheduling problem is a class of scheduling problems introduced for beam steering software of sophisticated radar devices, called phased arrays. Due to increasing popularity of such radars, the importance of coupled tasks scheduling is constantly growing. Unfortunately, most of the coupled tasks problems are NP-hard, and only a few practically usable algorithms for such problems were found. This paper provides a survey of already known complexity results of various variants of...
New representation to reduce the search space for the resource-constrained project scheduling problem
This paper describes a new representation for the solutions of the resource-constrained project scheduling problem (RCPSP) denoted Activity Set List. The most efficient heuristics for the problem use the activity list representation and the serial SGS method to construct the corresponding solution (schedule). The activity list may induce a search space of representations much larger then the space of schedules because the same schedule can correspond to many different activity list representations....
New solvable cases of m-machine and n-element sequencing problems
Note sur les problèmes d'ordonnancement PERT aléatoires
On a machine sequencing problem (I)
On minimizing total tardiness in a serial batching problem
We study the problem of scheduling jobs on a serial batching machine to minimize total tardiness. Jobs of the same batch start and are completed simultaneously and the length of a batch equals the sum of the processing times of its jobs. When a new batch starts, a constant setup time occurs. This problem s-batch is known to be NP-Hard in the ordinary sense. In this paper we show that it is solvable in pseudopolynomial time by dynamic programming.
On Minimizing Total Tardiness in a Serial Batching Problem
We study the problem of scheduling jobs on a serial batching machine to minimize total tardiness. Jobs of the same batch start and are completed simultaneously and the length of a batch equals the sum of the processing times of its jobs. When a new batch starts, a constant setup time s occurs. This problem 1|s-batch | ∑Ti is known to be NP-Hard in the ordinary sense. In this paper we show that it is solvable in pseudopolynomial time by dynamic programming.
On modelling planning under uncertainty in manufacturing.
We present a modelling framework for two-stage and multi-stage mixed 0-1 problems under uncertainty for strategic Supply Chain Management, tactical production planning and operations assignment and scheduling. A scenario tree based scheme is used to represent the uncertainty. We present the Deterministic Equivalent Model of the stochastic mixed 0-1 programs with complete recourse that we study. The constraints are modelled by compact and splitting variable representations via scenarios.
On scheduling models.
On the application of insertion techniques for job shop problems with setup times
On the application of insertion techniques for job shop problems with setup times
Constructive heuristics for shop scheduling problems are often based on priority (or dispatching) rules. However, recent work has demonstrated that insertion algorithms that step by step insert operations or jobs into partial schedules usually clearly outperform priority rules. In this paper, we consider various job shop scheduling problems with setup times. For each job a specific technological route and a release date are given. Moreover, the jobs are partitioned into groups. A sequence independent...
On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications
We consider the unit execution time unit communication time (UET-UCT) scheduling model with hierarchical communications [1], and we study the impact of the hierarchical communications hypothesis on the hardness of approximation. We prove that there is no polynomial time approximation algorithm with performance guarantee smaller than (unless ). This result is an extension of the result of Hoogeveen et al. [6] who proved that there is no polynomial time -approximation algorithm with for the...
On the hardness of approximating the UET-UCT scheduling problem with hierarchical communications
We consider the unit execution time unit communication time (UET-UCT) scheduling model with hierarchical communica tions [CITE], and we study the impact of the hierarchical communications hypothesis on the hardness of approximation. We prove that there is no polynomial time approximation algorithm with performance guarantee smaller than 5/4 (unless P = NP). This result is an extension of the result of Hoogeveen et al. [CITE] who proved that there is no polynomial time ρ-approximation algorithm...
On the minimum dummy-arc problem
On the Pallet Loading Problem
On the power of randomization for job shop scheduling with -units length tasks
In the job shop scheduling problem -units-, there are machines and each machine has an integer processing time of at most time units. Each job consists of a permutation of tasks corresponding to all machines and thus all jobs have an identical dilation . The contribution of this paper are the following results; (i) for jobs and every fixed , the makespan of an optimal schedule is at most , which extends the result of [3] for ; (ii) a randomized on-line approximation algorithm for -units-...
On the power of randomization for job shop scheduling with k-units length tasks
In the job shop scheduling problem k-units-Jm, there are m machines and each machine has an integer processing time of at most k time units. Each job consists of a permutation of m tasks corresponding to all machines and thus all jobs have an identical dilation D. The contribution of this paper are the following results; (i) for jobs and every fixed k, the makespan of an optimal schedule is at most D+ o(D), which extends the result of [3] for k=1; (ii) a randomized on-line approximation...