Modelling and scheduling a batch-type production on identical machines
type: Item
instance of: scholarly article
title: Modelling and scheduling a batch-type production on identical machines
zbMATH Open document ID: 0637.90047
DOI: 10.1016/0377-2217(88)90229-9
author: Tadeusz J. Sawik
published in: European Journal of Operational Research
publication date: 1988-01-01T00:00:00Z
review text: A new formulation and a near-optimal algorithm are presented for some variation of an NP-hard parallel scheduling problem with forest-type constraints and a \(C_{\max}\) optimality criterion where multiple performing of each operation is required. The problem is formulated using a state space approach. In the algorithm the priority in which the assignment of operations to machines is made is based on the level of operation in the graph of precedence constraints. The worst-case performance bound of the algorithm is given, and the average performance is illustrated with computational examples.
Mathematics Subject Classification ID: 90B30
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 4039619
zbMATH Keywords: production scheduling
zbMATH Keywords: heuristic
zbMATH Keywords: near-optimal algorithm
zbMATH Keywords: NP-hard parallel scheduling
zbMATH Keywords: graph of precedence constraints
zbMATH Keywords: worst-case performance bound
MaRDI profile type: Publication
full work available at URL: 0377-2217(88)90229-9
OpenAlex ID: W1983034791
cites work: Bounds on Multiprocessing Timing Anomalies
cites work: An Almost-Optimal Algorithm for the Assembly Line Scheduling Problem
cites work: Nonpreemptive LP-Scheduling on Homogeneous Multiprocessor Systems
cites work: Q3968746
cites work: Scheduling multi-operational tasks on nonidentical machines as a time- optimal control problem
cites work: Scheduling lots of dependent unit-time operations on identical machines to minimize schedule length
cites work: Q3773683
description: scientific article; zbMATH DE number 4039619