Approximability of scheduling with fixed jobs
type: Item
instance of: scholarly article
title: Approximability of scheduling with fixed jobs
zbMATH Open document ID: 0953.90025
author: Mark Scharbrodt
author: Angelika Steger
author: Horst Weisser
published in: Journal of Scheduling
publication date: 2001-02-01T00:00:00Z
review text: Scheduling problems of minimizing the makespan on identical parallel machines are among the most well-studied problems -- especially in the field of approximation. In modern industrial software however, it has become standard to work on a variant of this problem, where some of the jobs are already fixed in the schedule. The remaining jobs are to be assigned to the machines in such a way that they do not overlap with fixed jobs. This problem variant is the root of many real-world scheduling problems where pre-assignments on the machines are considered, such as cleaning times or jobs that have already started. In this paper the authors investigate the approximability of the scheduling problem with fixed jobs. They present a Polynomial-Time Approximation Scheme (PTAS) for the case that the number \(m\) of machines is constant. For this PTAS they propose a new technique by partitioning an underlying packing problem into a reasonable unrelated family of restricted bin packing problems. They also generalize the PTAS to the case that the machines are independent and run at different speeds. Moreover, they demonstrate that, assuming P\(\neq\)NP, there is no arbitrarily close approximation in the general case when the number of machines is part of the input. This is extended by showing that there is no asymptotic PTAS in the general machine case. We finally show that there exists no FPTAS in the constant machine case, unless P\(=\)NP. These results contrast to the classical problem of minimizing the makespan where the existence of a PTAS resp. of an FPTAS for the variable resp. the constant machine case has been proven.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 1402222
zbMATH Keywords: polynomial approximation scheme
zbMATH Keywords: scheduling
zbMATH Keywords: makespan
MaRDI profile type: Publication
cites work: Tighter Bounds for the Multifit Processor Scheduling Algorithm
cites work: Q4198056
cites work: Integer Programming with a Fixed Number of Variables
cites work: Bin packing can be solved within 1+epsilon in linear time
cites work: A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
cites work: An Application of Bin-Packing to Multiprocessor Scheduling
cites work: Bounds for Certain Multiprocessing Anomalies
DOI: 10.1002/(SICI)1099-1425(199911/12)2:6%3C267::AID-JOS31%3E3.0.CO;2-H
description: scientific article; zbMATH DE number 1402222