Scheduling a proportionate flow shop of batching machines

DOI10.1007/S10951-020-00667-2MaRDI QIDQ5919041zbMATH OpenOpenAlexFDO

Authors Christoph Hertrich, Christian H. Weiß, Heiner Ackermann, Sandy Heydrich, Sven O. Krumke

Publication date 11 December 2020

Published in Journal of Scheduling (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2006.09872

zbMATH Keywords

batching machinesdynamic programmingpermutation schedulesplanning of pharmaceutical productionproportionate flow shop

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Applications of mathematical programming (90C90)

Abstract: In this paper we study a proportionate flow shop of batching machines with release dates and a fixed number $mgeq2$ of machines. The scheduling problem has so far barely received any attention in the literature, but recently its importance has increased significantly, due to applications in the industrial scaling of modern bio-medicine production processes. We show that for any fixed number of machines, the makespan and the sum of completion times can be minimized in polynomial time. Furthermore, we show that the obtained algorithm can also be used to minimize the weighted total completion time, maximum lateness, total tardiness and (weighted) number of late jobs in polynomial time if all release dates are $0$. Previously, polynomial time algorithms have only been known for two machines.

Recommendations

• Scheduling a proportionate flow shop of batching machines
• Batching and scheduling in a multi-machine flow shop
• Online algorithms to schedule a proportionate flexible flow shop of batching machines
• Proportionate flowshops with general position-dependent processing times
• A note: Maximizing the weighted number of just-in-time jobs on a proportionate flowshop

Cites work

• A hybrid scheduling approach for a two-stage flexible flow shop with batch processing machines
• A polynomial-time algorithm for a flow-shop batching problem with equal-length operations
• A problem reduction and decomposition approach for scheduling for a flowshop of batch processing machines
• Analyzing and optimizing the throughput of a pharmaceutical production process
• Batching and scheduling in a multi-machine flow shop
• Batching and Scheduling Jobs on Batch and Discrete Processors
• Batching identical jobs
• Complexity results for single-machine problems with positive finish-start time-lags
• Domino sequencing: scheduling with state-based sequence-dependent setup times
• Efficient Algorithms for Scheduling Semiconductor Burn-In Operations
• Efficient scheduling algorithms for a single batch processing machine
• Integrated problem of soaking pit heating and hot rolling scheduling in steel plants
• Minimizing due date related performance measures on two batch processing machines
• Minimizing the number of tardy job units under release time constraints
• Optimal two- and three-stage production schedules with set-up time included
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Parallel batch scheduling of equal-length jobs with release and due dates
• Parameterized complexity of machine scheduling: 15 open problems
• Review of the ordered and proportionate flow shop scheduling research
• Scheduling a batching machine
• Scheduling algorithms
• Scheduling and fixed-parameter tractability
• Scheduling batches with simultaneous job processing for two-machine shop problems
• Scheduling parallel batching machines in a sequence
• Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem
• The assignment problem with nearly Monge arrays and incompatible partner indices
• The Complexity of Flowshop and Jobshop Scheduling

Cited in

(10)

• Batch scheduling on uniform machines to minimize total flow-time
• A problem reduction and decomposition approach for scheduling for a flowshop of batch processing machines
• Online algorithms to schedule a proportionate flexible flow shop of batching machines
• Review of the ordered and proportionate flow shop scheduling research
• Scheduling a proportionate flow shop of batching machines
• Scheduling a single machine with multiple due dates per job
• A systematic review of permutation flow shop scheduling with due-date-related objectives
• Two-agent proportionate flowshop scheduling with deadlines: polynomial-time optimization algorithms
• A joint scheduling approach for production and material handling under customized manufacturing paradigm
• Flow shops with machine maintenance: ordered and proportionate cases

This page was built for publication: Scheduling a proportionate flow shop of batching machines

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