𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the approximate tradeoff for bicriteria batching and parallel machine scheduling problems

✍ Scribed by Eric Angel; Evripidis Bampis; Alexander Kononov

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
305 KB
Volume
306
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We consider multiobjective scheduling problems, i.e. scheduling problems that are evaluated with respect to many cost criteria, and we are interested in determining a trade-o (Pareto curve) among these criteria. We study two types of bicriteria scheduling problems: single-machine batching problems and parallel machine scheduling problems. Instead of proceeding in a problem-byproblem basis, we identify a class of multiobjective optimization problems possessing a fully polynomial time approximation scheme (FPTAS) for computing an -approximate Pareto curve. This class contains a set of problems whose Pareto curve can be computed via a simple pseudo-polynomial dynamic program for which the objective and transition functions satisfy some, easy to verify, arithmetical conditions. Our study is based on a recent work of Woeginger (Electronic Colloquium on Computational Complexity, Report 84 (short version appeared in SODA'99, pp. 820 -829)) for the single criteria optimization ex-benevolent problems. We show how our general result can be applied to the considered scheduling problems.

πŸ“œ SIMILAR VOLUMES

An efficient branch-and-bound algorithm
An efficient branch-and-bound algorithm for the two-machine bicriteria flowshop scheduling problem
✍ Wei-Chang Yeh πŸ“‚ Article πŸ“… 2001 πŸ› Society of Manufacturing Engineers 🌐 English βš– 826 KB

In this study, the two-machine bicriteria flowshop scheduling problem is addressed. The objective is to minimize a weighted sum of total flowtime and makespan. Different branch-and-bound algorithms have already appeared in the literature for this problem. In this study, a more efficient branch-and-b

Genetic algorithms for the job-shop sche
Genetic algorithms for the job-shop scheduling problem with unrelated parallel constraints: Heuristic mixing method machines and precedence
✍ Fatima Ghedjati πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 360 KB

In this paper, we are interested in job-shop scheduling problems with several unrelated parallel machines and precedence constraints between the operations of the jobs (with either linear or non-linear process routings). The objective is to minimize the maximum completion time (Cmax). We propose an

An efficient branch-and-bound algorithm
An efficient branch-and-bound algorithm for the two-machine bicriteria flowshop scheduling problem : Wei-Chang Yeh, v20, n2, 2001, pp113–123
πŸ“‚ Article πŸ“… 2002 πŸ› Society of Manufacturing Engineers 🌐 English βš– 296 KB

and keyword index optimization, the infrastructure is capable of finding robust error recovery algorithms. It is expected that this approach will require less time for the generation of robust error recovery logic.