Submodular batch scheduling on parallel machines

DOI10.1002/NAV.22221MaRDI QIDQ7028660zbMATH OpenFDO

Authors Tao Sun, Jun-Qiang Wang, Guo-Qiang Fan, Zhixin Liu

Publication date 11 February 2025

Published in Naval Research Logistics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/NAV.22221

zbMATH Keywords

approximation algorithmbatch machineschedulingsubmodular functionworst-case performance ratio

Mathematics Subject Classification ID

Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35)

Cites work

• A coordination mechanism for a scheduling game with parallel-batching machines
• A survey of scheduling with parallel batch (p-batch) processing
• An analysis of approximations for maximizing submodular set functions—I
• Batch sizing and job sequencing on a single machine
• Batch-processing scheduling with setup times
• Best possible algorithms for online scheduling on identical batch machines with periodic pulse interruptions
• Bounded serial-batching scheduling for minimizing maximum lateness and makespan
• Bounds on Multiprocessing Timing Anomalies
• Efficient Algorithms for Scheduling Semiconductor Burn-In Operations
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Mixed batch scheduling on identical machines
• ON MINIMIZING TOTAL COMPLETION TIME IN BATCH MACHINE SCHEDULING
• On-line algorithms for minimizing makespan on batch processing machines
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Parallel-batch scheduling with rejection: structural properties and approximation algorithms
• Scheduling a batching machine
• Scheduling a single parallel-batching machine with non-identical job sizes and incompatible job families
• Scheduling Problems with Two Competing Agents
• Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime
• Single-machine and parallel-machine serial-batching scheduling problems with position-based learning effect and linear setup time
• Single-machine serial-batch delivery scheduling with two competing agents and due date assignment
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• The complexity of one-machine batching problems
• The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost
• Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes

Cited in

(1)

• Scheduling mixed batch machines with inclusive processing set restrictions and non-identical capacities

This page was built for publication: Submodular batch scheduling on parallel machines

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