This paper investigates the performance of a set of greedy algorithms for solving the Multi- Capacitated Metric Scheduling Problem (MCM-SP). All algorithms considered are variants of ESTA (Earliest Start Time Algorithm), previously proposed in [3]. The paper starts with an analysis of ESTA's performance on different classes of MCM-SP problems. ESTA is shown to be effective on several of these classes, but is also seen to have difficulty solving problems with heavy resource contention. Several possibilities for improving the basic algorithm are investigated. A first crucial modification consists of substituting ESTA's pairwise analysis of resource conflicts with a more aggregate and thus more powerful Minimal Critical Set (Mcs) computation. To cope with the combinatorial task of enumerating MCSs, several approximate sampling procedures are then defined. Some systematic sampling strategies, previously shown effective on a related but different class of scheduling problem, are found to be less effective on MCM-SP. On the contrary, a randomized mcs sampling technique is introduced, forming a variant of ESTA that is shown to be quite powerful on highly constrained problems.

Greedy algorithms for the Multi-Capacitated Metric Scheduling Problem

Cesta A;Oddi A;
2000

Abstract

This paper investigates the performance of a set of greedy algorithms for solving the Multi- Capacitated Metric Scheduling Problem (MCM-SP). All algorithms considered are variants of ESTA (Earliest Start Time Algorithm), previously proposed in [3]. The paper starts with an analysis of ESTA's performance on different classes of MCM-SP problems. ESTA is shown to be effective on several of these classes, but is also seen to have difficulty solving problems with heavy resource contention. Several possibilities for improving the basic algorithm are investigated. A first crucial modification consists of substituting ESTA's pairwise analysis of resource conflicts with a more aggregate and thus more powerful Minimal Critical Set (Mcs) computation. To cope with the combinatorial task of enumerating MCSs, several approximate sampling procedures are then defined. Some systematic sampling strategies, previously shown effective on a related but different class of scheduling problem, are found to be less effective on MCM-SP. On the contrary, a randomized mcs sampling technique is introduced, forming a variant of ESTA that is shown to be quite powerful on highly constrained problems.
2000
3-540-67866-2
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14243/18267
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact