Parallel machine scheduling with splitting jobs

DOI10.1016/S0166-218X(00)00176-1zbMath0962.90020OpenAlexW2082649910MaRDI QIDQ1570839

Wen-Xun Xing, Jia-Wei Zhang

Publication date: 21 June 2001

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00176-1

zbMATH Keywords

parallel machine schedulingworst-case analysissetup timesworst case analysisparallel machine scheduling (PMS) problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Resource loading with time windows ⋮ Scheduling with job-splitting considering learning and the vital-few law ⋮ A multi-objective optimization for preemptive identical parallel machines scheduling problem ⋮ Lot-sizing scheduling with batch setup times ⋮ Scheduling problems with rejection to minimize the \(k\)-th power of the makespan plus the total rejection cost ⋮ Strong LP formulations for scheduling splittable jobs on unrelated machines ⋮ Splitting versus setup trade-offs for scheduling to minimize weighted completion time ⋮ Two meta-heuristics for parallel machine scheduling with job splitting to minimize total tardiness ⋮ Scheduling cleaning activities on trains by minimizing idle times ⋮ Bounds for parallel machine scheduling with predefined parts of jobs and setup time ⋮ An enhanced formulation and simple heuristic for scheduling jobs on unrelated parallel machines ⋮ A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property ⋮ A survey of scheduling problems with setup times or costs ⋮ Rolling-horizon and fix-and-relax heuristics for the parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs ⋮ Integrated production and delivery scheduling on a serial batch machine to minimize the makespan ⋮ Parallel machine scheduling considering a job-splitting property ⋮ Scheduling uniform parallel dedicated machines with job splitting, sequence-dependent setup times, and multiple servers ⋮ An approximate algorithm for a high-multiplicity parallel machine scheduling problem ⋮ The crop growth planning problem in vertical farming ⋮ Batch sizing and just-in-time scheduling with common due date ⋮ Exact and approximate algorithms for high-multiplicity parallel machine scheduling ⋮ Split scheduling with uniform setup times

Cites Work

• Unnamed Item
• A new polynomial-time algorithm for linear programming
• A state-of-the-art review of parallel-machine scheduling research
• Scheduling with Deadlines and Loss Functions
• Worst-Case Analysis of Heuristic Algorithms
• Integrating Scheduling with Batching and Lot-Sizing: A Review of Algorithms and Complexity
• Performance Guarantees for Scheduling Algorithms
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• A Better Heuristic for Preemptive Parallel Machine Scheduling with Batch Setup Times
• Analysis of Heuristics for Preemptive Parallel Machine Scheduling with Batch Setup Times
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
• Scheduling Jobs on Several Machines with the Job Splitting Property