Performance guarantee of two simple priority rules for production scheduling

The paper presents analytical results concerning algorithms applied to off-line and on-line production scheduling problems. A problem is solved off-line if all the required information to solve it is known in advance; it is solved on-line if only incomplete knowledge about the entire problem input is available. Production planning is related to off-line scheduling and production control requires on-line scheduling. We present algorithms for both types of problems concentrating on machines with limited availability and show how the solution quality of two simple scheduling rules can be guaranteed in terms of a worst-case analysis.