Minimization of resource consumption under a given deadline in the two- processor flow-shop scheduling problem
type: Item
instance of: scholarly article
title: Minimization of resource consumption under a given deadline in the two- processor flow-shop scheduling problem
zbMATH Open document ID: 0685.90054
DOI: 10.1016/0020-0190(89)90009-4
author: Adam Janiak
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: The paper deals with an extension of the classical two-processor flow- shop problem. Given are the parameter of the process. The scheduler (the algorithm) has a choice as to how much processing time should be assigned to each task. The scheduler can save task processing time by strategic allocation of the resource (e.g. financial outlay, energy, memory, etc.), i.e. the time is inverse proportional to the amount of the resource used. The problem is to find a sequence of tasks and a resource allocation minimizing the total resource consumption under the given deadline common for all tasks. It may be shown that the decision version of this problem is NP-complete, even for the task models with identical derivatives with respect to resource amount on one of the processors and for task processing times independent of the resources on another processor. The reduction may be done either via partition or knapsack. Some efficiently solvable cases of the problem and four (simple and modified) heuristic algorithms are shown. Some generalizations of the proposed approach are also outlined.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4123511
zbMATH Keywords: two-processor flow-shop problem
zbMATH Keywords: resource allocation
zbMATH Keywords: total resource consumption
zbMATH Keywords: deadline
zbMATH Keywords: heuristic algorithms
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90009-4
OpenAlex ID: W2062163671
cites work: Q4658190
cites work: The Complexity of Flowshop and Jobshop Scheduling
cites work: Time-optimal control in a single machine problem with resource constraints
cites work: Optimal two- and three-stage production schedules with set-up time included
cites work: Q4142699
cites work: A bicriterion approach to time/cost trade-offs in sequencing
cites work: Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine
Recommended article: Two-machine flowshop scheduling problem with bounded processing times to minimize total completion time
Recommended article: Two-machine flow shop scheduling with convex resource consumption functions
Recommended article: Two-machine flow shop scheduling problems with minimal and maximal delays
Recommended article: Q4924332
Recommended article: Minmax due-date assignment on a two-machine flowshop
Recommended article: Two-machine flowshop minimum-length scheduling problem with random and bounded processing times
Recommended article: Two-machine flowshop scheduling to minimize mean flow time
Recommended article: Heuristics for the two-machine flowshop scheduling problem to minimize maximum lateness with bounded processing times
Recommended article: Scheduling on multiple two-stage flowshops with a deadline
Recommended article: Minimization of the makespan in a two-machine problem under given resource constraints
description: scientific article; zbMATH DE number 4123511