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...
On the weak robustness of fuzzy matrices
A matrix in -algebra (fuzzy matrix) is called weakly robust if is an eigenvector of only if is an eigenvector of . The weak robustness of fuzzy matrices are studied and its properties are proved. A characterization of the weak robustness of fuzzy matrices is presented and an algorithm for checking the weak robustness is described.
On transitive orientations of G-ê
A comparability graph is a graph whose edges can be oriented transitively. Given a comparability graph G = (V,E) and an arbitrary edge ê∈ E we explore the question whether the graph G-ê, obtained by removing the undirected edge ê, is a comparability graph as well. We define a new substructure of implication classes and present a complete mathematical characterization of all those edges.
One-machine scheduling with allocation of continuously-divisible resource and with no precedence constraints
One-machine sequencing with release dates, delivery times and precedence constraints
Open shop scheduling with delays
Optimal choice of parameters in machine-time scheduling problems with penalized earliness in starting and lateness in completing the operations
Optimal scheduling of material handling devices in a PCB production line: problem formulation and a polynomial algorithm.