Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines

Claire Hanen () and Alix Munier Kordon ()
Additional contact information
Claire Hanen: Sorbonne Université, CNRS, LIP6
Alix Munier Kordon: Sorbonne Université, CNRS, LIP6

Journal of Scheduling, 2024, vol. 27, issue 2, No 1, 119-133

Abstract: Abstract Scheduling problems involving a set of dependent tasks with release dates and deadlines on a limited number of resources have been intensively studied. However, few parameterized complexity results exist for these problems. This paper studies the existence of a feasible schedule for a typed task system with precedence constraints and time intervals $$(r_i,d_i)$$ ( r i , d i ) for each job i. The problem is denoted by $$P\vert \mathcal{M}_j(type),prec,r_i,d_i\vert \star $$ P | M j ( t y p e ) , p r e c , r i , d i | ⋆ . Several parameters are considered: the pathwidth pw(I) of the interval graph I associated with the time intervals $$(r_i, d_i)$$ ( r i , d i ) , the maximum processing time of a task $$p_{\max }$$ p max and the maximum slack of a task $$s\ell _{\max }$$ s ℓ max . This paper establishes that the problem is para- $$\textsf{NP}$$ NP -complete with respect to any of these parameters. It then provides a fixed-parameter algorithm for the problem parameterized by both parameters pw(I) and $$\min (p_{\max },s\ell _{\max })$$ min ( p max , s ℓ max ) . It is based on a dynamic programming approach that builds a levelled graph which longest paths represent all the feasible solutions. Fixed-parameter algorithms for the problems $$P\vert \mathcal{M}_j(type),prec,r_i,d_i\vert C_{\max }$$ P | M j ( t y p e ) , p r e c , r i , d i | C max and $$P\vert \mathcal{M}_j(type),prec,r_i\vert L_{\max }$$ P | M j ( t y p e ) , p r e c , r i | L max are then derived using a binary search.

Keywords: Fixed-parameter tractable algorithm; Precedence constraints; Typed task system (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-023-00788-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:27:y:2024:i:2:d:10.1007_s10951-023-00788-4

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-023-00788-4

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().