Performance guarantees for a scheduling problem with common stepwise job payoffs

DOI10.1016/j.tcs.2014.10.010zbMath1303.90052OpenAlexW2093589474MaRDI QIDQ476886

Yasmina Seddik, Safia Kedad-Sidhoum, Christophe Gonzales

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.10.010

zbMATH Keywords

schedulingrelease datesabsolute approximation guaranteerelative approximation guaranteestepwise payoffs

Mathematics Subject Classification ID

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

Related Items (1)

Heuristics for a flowshop scheduling problem with stepwise job objective function

Cites Work

• Single-machine scheduling with stepwise tardiness costs and release times
• Single processor scheduling with job values depending on their completion times
• On the complexity of generalized due date scheduling problems
• An exact approach for scheduling jobs with regular step cost functions on a single machine
• Scheduling jobs on parallel machines to minimize a regular step total cost function
• Single machine scheduling with delivery dates and cumulative payoffs
• Scheduling with Fixed Delivery Dates
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints

This page was built for publication: Performance guarantees for a scheduling problem with common stepwise job payoffs