We study the problem of multimode scheduling tasks on dedicated processors, with the objective of minimizing the maximum completion time. Each task can be undertaken in one among a set of predefined alternative modes, where each mode specifies a required set of dedicated processors and a processing time. At any time each processor can be used by a single task at most. General precedence constraints exist among tasks, and task preemption is not allowed. The problem consists of assigning a mode and a starting time to each task, respecting processor and precedence constraints, to minimize the time required to complete all tasks. The problem is NP-hard in several particular cases. In previous works, we studied algorithms in which a solution was obtained by means of an iterative procedure that combines mode assignment and sequencing phases separately. In this paper, we present some new heuristics where the decision on the mode assignment is taken on the basis of a partial schedule. Then, for each task, the mode selection and the starting time are chosen simultaneously considering the current processor usage. Different lower bounds are derived from a mathematical formulation of the problem and from a graph representation of a particular relaxed version of the problem. Heuristic solutions and lower bounds are evaluated on randomly generated test problems.

Bianco, L., Dell'Olmo, P., Giordani, S., Speranza, M. (1999). Minimizing makespan in a multimode multiprocessor shop scheduling problem. NAVAL RESEARCH LOGISTICS, 46(8), 893-911 [10.1002/(SICI)1520-6750(199912)46:8<893::AID-NAV2>3.0.CO;2-7].

Minimizing makespan in a multimode multiprocessor shop scheduling problem

BIANCO, LUCIO;GIORDANI, STEFANO;
1999-01-01

Abstract

We study the problem of multimode scheduling tasks on dedicated processors, with the objective of minimizing the maximum completion time. Each task can be undertaken in one among a set of predefined alternative modes, where each mode specifies a required set of dedicated processors and a processing time. At any time each processor can be used by a single task at most. General precedence constraints exist among tasks, and task preemption is not allowed. The problem consists of assigning a mode and a starting time to each task, respecting processor and precedence constraints, to minimize the time required to complete all tasks. The problem is NP-hard in several particular cases. In previous works, we studied algorithms in which a solution was obtained by means of an iterative procedure that combines mode assignment and sequencing phases separately. In this paper, we present some new heuristics where the decision on the mode assignment is taken on the basis of a partial schedule. Then, for each task, the mode selection and the starting time are chosen simultaneously considering the current processor usage. Different lower bounds are derived from a mathematical formulation of the problem and from a graph representation of a particular relaxed version of the problem. Heuristic solutions and lower bounds are evaluated on randomly generated test problems.
1999
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore MAT/09 - RICERCA OPERATIVA
English
Con Impact Factor ISI
Algorithms; Computational complexity; Constraint theory; Graph theory; Heuristic methods; Iterative methods; Dedicated processors; Heuristic algorithms; Lower bounds; Multiple modes; Shop scheduling; Scheduling
Bianco, L., Dell'Olmo, P., Giordani, S., Speranza, M. (1999). Minimizing makespan in a multimode multiprocessor shop scheduling problem. NAVAL RESEARCH LOGISTICS, 46(8), 893-911 [10.1002/(SICI)1520-6750(199912)46:8<893::AID-NAV2>3.0.CO;2-7].
Bianco, L; Dell'Olmo, P; Giordani, S; Speranza, M
Articolo su rivista
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/2108/52333
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 10
social impact