Displaying similar documents to “Job shop scheduling with unit length tasks”

Job shop scheduling with unit length tasks

Meike Akveld, Raphael Bernhard (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

In this paper, we consider a class of scheduling problems that are among the fundamental optimization problems in operations research. More specifically, we deal with a particular version called . Using the results of Hromkovič, Mömke, Steinhöfel, and Widmayer presented in their work , we analyze the problem setting for 2 jobs with an unequal number of tasks. We contribute a deterministic algorithm which achieves a vanishing delay in...

On the application of insertion techniques for job shop problems with setup times

Yuri N. Sotskov, Thomas Tautenhahn, Frank Werner (2010)

RAIRO - Operations Research

Similarity:

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

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

An Improved Algorithm for a Bicriteria Batching Scheduling Problem

Cheng He, Xiumei Wang, Yixun Lin, Yundong Mu (2013)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

This note is concerned with the bicriteria scheduling problem on a series-batching machine to minimize maximum cost and makespan. An ( ) algorithm has been established previously. Here is an improved algorithm which solves the problem in ( ) time.

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

On the median-of-k version of Hoare's selection algorithm

Rudolf Grübel (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

In Hoare's (1961) original version of the algorithm   the partitioning element in the central divide-and-conquer step is chosen uniformly at random from the set in question. Here we consider a variant where this element is the median of a sample of size from . We investigate convergence in distribution of the number of comparisons required and obtain a simple explicit result for the limiting average performance of the median-of-three version.

Une méthode tabou pour l'ordonnancement multiprocesseur avec délais de communication

Dalila Tayachi, Philippe Chrétienne, Khaled Mellouli (2010)

RAIRO - Operations Research

Similarity:

This paper deals with the problem of scheduling tasks on identical processors in the presence of communication delays. A new approach of modelisation by a decision graph and a resolution by a tabu search method is proposed. Initial solutions are constructed by list algorithms, and then improved by a tabu algorithm operating in two phases. The experiments carried on arbitrary graphs show the efficiency of our method and that it outperformed the principle existent heuristics. ...

Convergence Rates of the POD–Greedy Method

Bernard Haasdonk (2013)

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique

Similarity:

Iterative approximation algorithms are successfully applied in parametric approximation tasks. In particular, reduced basis methods make use of the so-called Greedy algorithm for approximating solution sets of parametrized partial differential equations. Recently, convergence rate statements for this algorithm have been given (Buffa 2009, Binev 2010). The goal of the current study is the extension to time-dependent problems, which are typically approximated using the POD–Greedy algorithm...

Advice Complexity and Barely Random Algorithms

Dennis Komm, Richard Královič (2011)

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

Similarity:

Recently, a new measurement – the – was introduced for measuring the information content of online problems. The aim is to measure the bitwise information that online algorithms lack, causing them to perform worse than offline algorithms. Among a large number of problems, a well-known scheduling problem, , and the problem were analyzed within this model. We observe some connections between advice complexity and randomization. Our special focus goes to barely random algorithms, , randomized...