Approximation algorithms for bicriteria scheduling problems on identical parallel machines for makespan and total completion time

DOI10.1016/j.ejor.2022.06.021OpenAlexW4283068302WikidataQ114184264 ScholiaQ114184264MaRDI QIDQ2098029

Kangbok Lee, Xiaojuan Jiang, Michael L. Pinedo

Publication date: 17 November 2022

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2022.06.021

zbMATH Keywords

schedulingapproximation algorithmmakespantotal completion timeinapproximability

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Related Items (1)

Approximation algorithms for coupled task scheduling minimizing the sum of completion times

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast approximation algorithms for bi-criteria scheduling with machine assignment costs
• Total completion time minimization on multiple machines subject to machine availability and makespan constraints
• Bicriteria approximation algorithms for scheduling problems with communications delays
• A DP algorithm for minimizing makespan and total completion time on a series-batching machine
• Algorithms minimizing mean flow time: Schedule-length properties
• On the existence of schedules that are near-optimal for both makespan and total weighted completion time
• Heuristics for scheduling in flowshop with multiple objectives
• On the approximate tradeoff for bicriteria batching and parallel machine scheduling problems.
• A bicriteria approximation algorithm for the \(k\)-center and \(k\)-median problems
• Scheduling unit processing time jobs on a single machine with multiple criteria
• Two-machine flowshop scheduling with a secondary criterion
• Balancing minimum spanning trees and shortest-path trees
• Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time
• Ideal schedules in parallel machine settings
• Optimal scheduling for two-processor systems
• Multicriteria scheduling
• Approximation Techniques for Average Completion Time Scheduling
• Competitive Two-Agent Scheduling and Its Applications
• Bicriteria optimisation of the makespan and mean flowtime on two identical parallel machines
• Scheduling Problems with Two Competing Agents
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• On the Minimization of the Makespan Subject to Flowtime Optimality
• Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems
• Scheduling independent tasks to reduce mean finishing time
• Bounds on Multiprocessing Timing Anomalies

This page was built for publication: Approximation algorithms for bicriteria scheduling problems on identical parallel machines for makespan and total completion time