Approximation schemes for scheduling on uniformly related and identical parallel machines (Q1879359): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00453-003-1077-7 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2619122734 / rank | |||
Normal rank |
Latest revision as of 20:04, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Approximation schemes for scheduling on uniformly related and identical parallel machines |
scientific article |
Statements
Approximation schemes for scheduling on uniformly related and identical parallel machines (English)
0 references
22 September 2004
0 references
The article treats a scheduling problem with \(n\) jobs \((i,\) processing times (with speed 1) \(pi)\) on \(m\) uniformly related parallel machines, i.e., each machine \(j\) has an assigned speed \((sj)\) and the processing times of the jobs are inversely related to this machine-speed \((pij=pi/sj)\). The objective function is stated in a very general form, s.t. Minimal- maximum- and Minimal-Sum-functions can be treated. Therefore most of the objective functions lead to NP-hard problems. Based on this fact, the authors try to define a set of efficient schedules (which have a chance of being optimal), and formulate an approximation scheme producing a solution whose objective function value is within a certain bound to the (unknown) optimal solution. The main instrument for contructing the approximation is rounding the data to a level which is required by the accuracy of the approximative solution (nearer to the optimum means dealing with larger data and increasing the computational effort).
0 references