The use of integer linear programs for solving complex real-time scheduling problems is investigated. The problem of scheduling a workload represented as a directed acyclic graph (DAG) upon a dedicated multiprocessor platform is considered, in which each individual vertex of the DAG is assigned to a specific processor and the entire DAG is required to complete execution within a specified duration. A representation of this scheduling problem as a zero-one integer linear program is obtained. Some guidelines are proposed for identifying scheduling problems amenable to solution by converting to integer linear programs.
展开▼
