An FPTAS for parallel-machine scheduling under a grade of service provision to minimize makespan

DOI10.1016/j.ipl.2008.04.021zbMath1191.68102OpenAlexW2120200272MaRDI QIDQ975438

Min Ji, Cheng, T. C. Edwin

Publication date: 9 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10397/476

zbMATH Keywords

schedulingmakespangrade of serviceeligibility

Mathematics Subject Classification ID

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

Related Items

Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration, Two parallel-machine scheduling problems with function constraint, Group scheduling with deteriorating jobs to minimize the total weighted number of late jobs, Optimal algorithms for semi-online machine covering on two hierarchical machines, Single-machine scheduling with a nonlinear deterioration function, TWO APPROXIMATION SCHEMES FOR SCHEDULING ON PARALLEL MACHINES UNDER A GRADE OF SERVICE PROVISION, Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan, Uniform parallel machine scheduling with resource consumption constraint, A comment on parallel-machine scheduling under a grade of service provision to minimize makespan, Multipurpose machine scheduling with rejection and identical job processing times, Optimal algorithm for semi-online scheduling on two machines under GoS levels, Scheduling parallel machines with inclusive processing set restrictions and job release times, Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs, Single-machine batch scheduling of linear deteriorating jobs

Cites Work

• An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan
• Online and semi-online scheduling of two machines under a grade of service provision
• A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs
• Parallel machine scheduling under a grade of service provision
• Parallel-machine scheduling with simple linear deterioration to minimize total completion time
• Optimal online algorithms for scheduling on two identical machines under a grade of service
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem
• Online Scheduling on Parallel Machines with Two GoS Levels