A new approximation algorithm for unrelated parallel machine scheduling with release dates
DOI10.1007/s10479-019-03346-4zbMath1429.90028OpenAlexW2966192810WikidataQ127435289 ScholiaQ127435289MaRDI QIDQ2289003
Zhi Pei, Ziteng Wang, Mingzhong Wan
Publication date: 20 January 2020
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10479-019-03346-4
approximation algorithmbranch-and-boundsemi-definite programmingrelease datesunrelated parallel machine scheduling
Semidefinite programming (90C22) Convex programming (90C25) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Quadratic programming (90C20) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items (2)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem
- Solution algorithms for unrelated machines minmax regret scheduling problem with interval processing times and the total flow time criterion
- Approximate algorithms for unrelated machine scheduling to minimize makespan
- A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates
- Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms
- On modelling the maximum workload allocation for parallel unrelated machines with setups
- A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
- Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem
- An analysis of heuristics for the parallel-machine flexible-resource scheduling problem
- A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
- On the minimization of total weighted flow time with identical and uniform parallel machines
- Heuristics based on partial enumeration for the unrelated parallel processor scheduling problem
- GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times
- Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan
- A further study on two-agent parallel-batch scheduling with release dates and deteriorating jobs to minimize the makespan
- Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates
- An exact extended formulation for the unrelated parallel machine total weighted completion time problem
- A \((2 + \epsilon)\)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
- Parallel Machine Scheduling by Column Generation
- Experimental Comparison of Approximation Algorithms for Scheduling Unrelated Parallel Machines
- A new Lagrangian Relaxation Algorithm for scheduling dissimilar parallel machines with release dates
- Unrelated Machine Scheduling with Stochastic Processing Times
- Convex quadratic and semidefinite programming relaxations in scheduling
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Task Scheduling in Networks
- Solving Parallel Machine Scheduling Problems by Column Generation
- CSDP, A C library for semidefinite programming
- Scheduling Unrelated Machines by Randomized Rounding
- Semidefinite relaxations for partitioning, assignment and ordering problems
This page was built for publication: A new approximation algorithm for unrelated parallel machine scheduling with release dates
