Two machine mixed shop scheduling problem with controllable machine speeds
type: Item
instance of: scholarly article
title: Two machine mixed shop scheduling problem with controllable machine speeds
zbMATH Open document ID: 0615.90061
DOI: 10.1016/0166-218X(87)90005-9
author: Hiroaki Ishii
author: Teruo Masuda
author: Toshio Nishida
published in: Discrete Applied Mathematics
publication date: 1987-01-01T00:00:00Z
review text: The paper considers a two machine scheduling problem in which the objective is to determine an optimal machine speed pair and an optimal schedule. Each job consists of two operations. We have a mixed shop scheduling problem which means that for a subset of the jobs the order of processing on the machines is fixed (flow shop) and for the remaining jobs the order is free (open shop). The machine speeds are controllable. The objective function takes the form \(C_ 0t^{q_ 1}_{\max}+C_ 1(s')^{q_ 2}+C_ 2(t')^{q_ 2}\), where \(C_ 0\), \(C_ 1\), \(C_ 2\), \(q_ 1\), \(q_ 2\) are constant, \(t_{\max}\) is the makespan of the schedule, s' and t' are the speeds of the two machines. An \(0(n^ 2 \log n)\) algorithm is presented to solve this problem assuming that power and root of the functions encountered in the algorithm can be calculated in constant time.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3997539
zbMATH Keywords: uniform machines
zbMATH Keywords: controllable speed
zbMATH Keywords: two machine scheduling
zbMATH Keywords: optimal machine speed pair
zbMATH Keywords: optimal schedule
zbMATH Keywords: mixed shop scheduling
MaRDI profile type: Publication
cites work: Open Shop Scheduling to Minimize Finish Time
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: The mixed shop scheduling problem
cites work: Combinatorial Optimization with Rational Objective Functions
full work available at URL: 0166-218x(87)90005-9
OpenAlex ID: W2100173285
description: scientific article; zbMATH DE number 3997539