Two machine mixed shop scheduling problem with controllable machine speeds

DOI10.1016/0166-218X(87)90005-9MaRDI QIDQ1821024zbMATH OpenOpenAlexFDO

Authors Hiroaki Ishii, Teruo Masuda, Toshio Nishida

Publication date 1987

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(87)90005-9

zbMATH Keywords

controllable speedmixed shop schedulingoptimal machine speed pairoptimal scheduletwo machine schedulinguniform machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

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.

Recommendations

• TWO MACHINE OPEN SHOP SCHEDULING PROBLEM WITH CONTROLLABLE MACHINE SPEEDS
• A controlable two-machine flowshop scheduling problem
• scientific article; zbMATH DE number 4010197
• Two machine flow shop scheduling problem with no wait in process: Controllable machine speeds
• An O(n log n) Algorithm for the Two-Machine Flow Shop Problem with Controllable Machine Speeds

Cites work

• A Generalized Uniform Processor System
• Combinatorial Optimization with Rational Objective Functions
• Open Shop Scheduling to Minimize Finish Time
• Optimal two- and three-stage production schedules with set-up time included
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• The mixed shop scheduling problem

Cited in

(14)

• The mixed shop scheduling problem
• One machine scheduling problem with fuzzy duedates
• Optimal makespan scheduling with given bounds of processing times
• Two machine flow shop scheduling problem with no wait in process: Controllable machine speeds
• Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches
• Single machine scheduling with controllable release and processing parameters
• TWO MACHINE OPEN SHOP SCHEDULING PROBLEM WITH CONTROLLABLE MACHINE SPEEDS
• Optimal choice of machine speeds for two-stage non-homogeneous systems
• An O(n log n) Algorithm for the Two-Machine Flow Shop Problem with Controllable Machine Speeds
• Two-machine flowshop minimum-length scheduling problem with random and bounded processing times
• Scheduling problems with rejection to minimize the \(k\)-th power of the makespan plus the total rejection cost
• Single machine scheduling with rejection to minimize the \(k\)-th power of the makespan
• An adapted constraint-programming formulation of the resource-constrained project scheduling problem applied to the identical parallel machines group shop and mixed shop scheduling problems
• Bicriteria permutation flow shop scheduling problems with machine-dependent convex resource consumption functions

This page was built for publication: Two machine mixed shop scheduling problem with controllable machine speeds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1821024)