Displaying similar documents to “An Improved Algorithm for a Bicriteria Batching Scheduling Problem”

Minimizing the Earliness and Tardiness Cost of a Sequence of Tasks on a Single Machine

Philippe Chrétienne (2010)

RAIRO - Operations Research

Similarity:

Assume that tasks must be processed by one machine in a fixed sequence. The processing time, the preferred starting time and the earliness and tardiness costs per time unit are known for each task. The problem is to allocate each task a starting time such that the total cost incurred by the early and tardy tasks is minimum. Garey have proposed a nice log) algorithm for the special case of symmetric and task-independent costs. In this paper we first extend that algorithm to...

New algorithms for coupled tasks scheduling – a survey

Jacek Blazewicz, Grzegorz Pawlak, Michal Tanas, Wojciech Wojciechowicz (2012)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

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...

Analysis of a near-metric TSP approximation algorithm

Sacha Krug (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The traveling salesman problem (TSP) is one of the most fundamental optimization problems. We consider the -metric traveling salesman problem ( -TSP), , the TSP restricted to graphs satisfying the -triangle inequality ({}) ≤ (({}) + ({})), for some cost function and any three vertices . The well-known path matching Christofides algorithm (PMCA) guarantees an approximation ratio of 3 /2 and is the best known algorithm for the -TSP, for 1 ≤  ≤ 2....

On Minimizing Total Tardiness in a Serial Batching Problem

Philippe Baptiste, Antoine Jouglet (2010)

RAIRO - Operations Research

Similarity:

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 | ∑ 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.

Solving multi-agent scheduling problems on parallel machines with a global objective function

F. Sadi, A. Soukhal, J.-C. Billaut (2014)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

In this study, we consider a scheduling environment with ( ≥ 1) parallel machines. The set of jobs to schedule is divided into disjoint subsets. Each subset of jobs is associated with one agent. The agents compete to perform their jobs on common resources. The objective is to find a schedule that minimizes a global objective function , while maintaining the regular objective function of each agent, , at a level no greater than a fixed value, ...

About the choice of the variable to unassign in a decision repair algorithm

Cédric Pralet, Gérard Verfaillie (2010)

RAIRO - Operations Research

Similarity:

The algorithm (Jussien and Lhomme, (2002) 21–45), which has been designed to solve (CSP), can be seen, either (i) as an extension of the classical algorithm with the introduction of a free choice of the variable to which to backtrack in case of inconsistency, or (ii) as a algorithm in the space of the partial consistent variable assignments. or (iii) as a hybridisation between and . Experiments reported in Pralet and Verfailllie (2004) show that some heuristics...

Inequality-sum: a global constraint capturing the objective function

Jean-Charles Régin, Michel Rueher (2010)

RAIRO - Operations Research

Similarity:

This paper introduces a new method to prune the domains of the variables in constrained optimization problems where the objective function is defined by a sum , and where the integer variables are subject to difference constraints of the form . An important application area where such problems occur is deterministic scheduling with the as optimality criteria. This new constraint is also more general than a sum constraint defined on a set of ordered variables. Classical...

Computing and proving with pivots

Frédéric Meunier (2013)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

A simple idea used in many combinatorial algorithms is the idea of . Originally, it comes from the method proposed by Gauss in the 19th century for solving systems of linear equations. This method had been extended in 1947 by Dantzig for the famous simplex algorithm used for solving linear programs. From since, a pivoting algorithm is a method exploring subsets of a ground set and going from one subset to a new one ′ by deleting an element inside and adding an element outside : ′ =  ...

Bottleneck Capacity Expansion Problems with General Budget Constraints

Rainer E. Burkard, Bettina Klinz, Jianzhong Zhang (2010)

RAIRO - Operations Research

Similarity:

This paper presents a unified approach for bottleneck capacity expansion problems. In the bottleneck capacity expansion problem, BCEP, we are given a finite ground set , a family of feasible subsets of and a nonnegative real capacity ĉ for all . Moreover, we are given monotone increasing cost functions for increasing the capacity of the elements as well as a budget . The task is to determine new capacities c ≥ ĉ such that the objective function given by...

An Extended Opportunity-Based Age Replacement Policy

Bermawi P. Iskandar, Hiroaki Sandoh (2010)

RAIRO - Operations Research

Similarity:

The present study proposes an extended opportunity-based age replacement policy where opportunities occur according to a Poisson process. When the age, of the system satisfies for a prespecified value , a corrective replacement is conducted if the objective system fails. In case satisfies for another prespecified value , we take an opportunity to preventively replace the system by a new one with probability , and do not take the opportunity with probability . At the moment reaches...

A note on a two dimensional knapsack problem with unloading constraints

Jefferson Luiz Moisés da Silveira, Eduardo Candido Xavier, Flávio Keidi Miyazawa (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

In this paper we address the two-dimensional knapsack problem with unloading constraints: we have a bin , and a list of rectangular items, each item with a class value in {1,...,}. The problem is to pack a subset of into , maximizing the total profit of packed items, where the packing must satisfy the unloading constraint: while removing one item , items with higher class values can not block . We present a (4 + )-approximation algorithm when the bin is a square. We also present (3 + )-approximation...