A survey of results for sequencing problems with controllable processing times
type: Item
instance of: scholarly article
title: A survey of results for sequencing problems with controllable processing times
zbMATH Open document ID: 0693.90056
DOI: 10.1016/0166-218X(90)90105-L
published in: Discrete Applied Mathematics
publication date: 1990-01-01T00:00:00Z
review text: This paper reviews algorithms and complexity results for scheduling problems in which the processing time of a job is a decision variable. For each job, an upper and lower bound on its processing time is specified and a processing cost, which is a linear decreasing function of processing time, is given. In addition to the processing cost, a schedule cost (maximum completion time, maximum lateness or total weighted completion time, for example) is associate with completion times of the jobs. Most results relate to the problem of scheduling a single machine to minimize the processing plus schedule cost. Throughout the paper, a typical algorithm first selects a processing order of the jobs and then solves a linear program to fix the processing times; this linear program can often be solved very efficiently. For some problems, this type of algorithm provides an exact solution; for others, it is a heuristic and worst-case performance bounds are available.
reviewed by: C.N.Potts
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68M20
zbMATH DE Number: 4135701
zbMATH Keywords: controllable processing time
zbMATH Keywords: upper bound
zbMATH Keywords: complexity results
zbMATH Keywords: lower bound
zbMATH Keywords: maximum completion time
zbMATH Keywords: maximum lateness
zbMATH Keywords: total weighted completion time
zbMATH Keywords: single machine
zbMATH Keywords: heuristic
zbMATH Keywords: worst-case performance
author: Eugeniusz Nowicki
author: Stanisław Zdrzałka
MaRDI profile type: Publication
cites work: Scheduling subject to resource constraints: Classification and complexity
cites work: The Theory of Networks and Management Science. Part I
cites work: Job-shop scheduling with resource-time models of operations
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: A Generalized Uniform Processor System
cites work: Optimal two- and three-stage production schedules with set-up time included
cites work: Minimizing maximum lateness on one machine: computational experience and some applications
cites work: Q4130999
cites work: A Functional Equation and its Application to Resource Allocation and Sequencing Problems
cites work: Q4055377
cites work: A two-machine flow shop scheduling problem with controllable job processing times
cites work: Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
cites work: Q3329208
cites work: Multiobjective network scheduling with efficient use of renewable and nonrenewable resources
cites work: Resource-Constrained Project Scheduling with Time-Resource Tradeoffs: The Nonpreemptive Case
cites work: Q3690568
cites work: Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine
cites work: A bicriterion approach to time/cost trade-offs in sequencing
full work available at URL: 0166-218x(90)90105-l
OpenAlex ID: W2020909460
description: scientific article; zbMATH DE number 4135701