Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan
type: Item
instance of: scholarly article
title: Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan
zbMATH Open document ID: 1206.90043
author: Cheng He
author: Jinjiang Yuan
author: Yanpei Liu
published in: Theoretical Computer Science
publication date: 2007-09-03T00:00:00Z
review text: This paper studies the bicriteria problem of scheduling \(n\) jobs on a batching machine to minimize maximum lateness and makespan simultaneously. The authors consider the parallel-batching model in which the jobs that are processed together form a batch with the same starting time and completion time, and the processing time of a batch is equal to the largest processing time of jobs in it. A parallel-batching machine can handle up to \(b\) jobs in a batch. The authors analyse the unbounded model in which the number of jobs in each batch is unlimited, denoted by \(``b\geq n"\) in short. Based on the result by [\textit{P. Brucker, A. Gladky, H. Hoogeveen, M. Y. Kovalyov, C. N. Potts, T. Tautenhahn} and \textit{S. L. van de Velde}, J. Sched. 1, No. 1, 31--54 (1998; Zbl 0909.90172)], the authors show that for the bicriteria problem under consideration one can order the jobs according to the well-known SPT rule and then form an optimal schedule, specified by the jobs that start each batch. In the paper a dynamic programming algorithm (DP-algorithm) is developed to find a Pareto optimal schedule for the bicriteria problem. The running time of DP-algorithm is \(O(n)\). To generate all Pareto optimal solutions, a basic method is the so-called \(\epsilon\)-constrained approach (see \textit{H. Hoogeveen} [Eur. J. Oper. Res. 167, No. 3, 592--623 (2005; Zbl 1154.90458)]). Using this approach and the DP algorithm, the authors demonstrate how to produce all Pareto optimal solutions to the problem under consideration in \(O(n^3)\) time. The number of Pareto optimal schedules for this bicriteria problem is proved to be at most \(n(n-1)/2 +1\).
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68M20
zbMATH DE Number: 5186618
zbMATH Keywords: multicriteria scheduling
zbMATH Keywords: batching machine
zbMATH Keywords: maximum lateness
zbMATH Keywords: Pareto optimal solutions
reviewed by: I. N. Lushchakova
MaRDI profile type: Publication
full work available at URL: j.tcs.2007.04.034
OpenAlex ID: W2018793254
cites work: Scheduling Problems with Two Competing Agents
cites work: Scheduling a batching machine
cites work: A multiple-criterion model for machine scheduling
cites work: Q2734595
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: Multicriteria scheduling
cites work: Single-Machine Scheduling to Minimize a Function of Two or Three Maximum Cost Criteria
cites work: Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time
DOI: 10.1016/J.TCS.2007.04.034
Recommended article: Q3070927
Recommended article: Bounded serial-batching scheduling for minimizing maximum lateness and makespan
Recommended article: Bicriteria scheduling on a series-batching machine to minimize maximum cost and makespan
Recommended article: An improved algorithm on unbounded parallel-batching scheduling to minimize maximum cost and makespan
Recommended article: Bicriteria scheduling on an unbounded parallel-batch machine for minimizing makespan and maximum cost
Recommended article: BATCHING MACHINE SCHEDULING WITH BICRITERIA: MAXIMUM COST AND MAKESPAN
Recommended article: A DP algorithm for minimizing makespan and total completion time on a series-batching machine
Recommended article: A Single Machine Bicriterion Scheduling Problem and an Optimizing Branch-and-Bound Procedure
Recommended article: An improved algorithm for a bicriteria batching scheduling problem
Recommended article: Q3405330
description: scientific article; zbMATH DE number 5186618