online convergent scheduling: un approccio per lo scheduling di job batch su griglia

  

  !"#$" %&$' "( ) '" * $'*(+ $ *,-") '.$

/012 32 456705

89:;9< =>9?<@A<9B CDE<FG:;9A

#* "&&''  &$ ( '.$#( *+  HI I")'. # + +( "

"* ")J KLMNOPQP RLSLTTOTO ") '(" UVWUXY $(") J ZLTOPNO [LNL\QOL ]L^NL ZO__O $(")$J `OP\a b^SSOT

q rTsNad^tOaTP h YuY &)"   '$'" u u u u u u u u u u u u u u u u u u u u u u u u W Yu U *"(  $( &I($-" u u u u u u u u u u u u u u u u u u u u u u u v Yu UuY I($- $'  *"( u u u u u u u u u u u u u u u u u u u w Yu UuU % )$- $"(x) -$ u u u u u u u u u u u u u u u u u u u u u y YuX %)") $((z")$ u u u u u u u u u u u u u u u u u u u u u u u u u u u YY Yu{ *|$+$*) '.$#( *+ u u u u u u u u u u u u u u u u u u u u u u YU Yu W "))"-$*) u u u u u u u u u u u u u u u u u u u u u u u u u u u u Y{ f }^NO~sO_P q€ UuY $"( *$ u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u Yy Uu U *&#) u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u Uw UuX  * - " *$ $((z|$.$" u u u u u u u u u u u u u u u u u u XU Uu{  * - " *$ $((z"))$" -$ " u u u u u u u u u u u u u u u u XU Uu W $‚#  ) - * - u u u u u u u u u u u u u u u u u u u u u u u u u X{ Uuv *) *|$''. "-$*) u u u u u u u u u u u u u u u u u u u u u u u u XW Uu w -"( " *$ u u u u u u u u u u u u u u u u u u u u u u u u u u XW Uuy * $" * ƒ*"( u u u u u u u u u u u u u u u u u u u u u u u Xv UuyuY $$-&) * u u u u u u u u u u u u u u u u u u u u u u u u Xv UuyuU #* *+ u u u u u u u u u u u u u u u u u u u u u u u u u u u Xw „ ]O_PTtP „… XuY *)# *$ u u u u u u u u u u u u u u u u u u u u u u u u u u u u X† Xu U # ) '"  )) - " *$ u u u u u u u u u u u u u u u u u u u u {U XuX (#)$ *+ u u u u u u u u u u u u u u u u u u u u u u u u u u u u u { y

Xu{ $-")'. *+J "--  I ( )Œ $ '(#)$ u u u u u u u u u u u u u WV Xu{uY (+ )- I"*'.  I#* u u u u u u u u u u u u u u u u WU Xu{u U (+ )- +$$Ž u u u u u u u u u u u u u u u u u u u u u Ww  Ls_OT\ jh {uY  '$'" $ -" - u u u u u u u u u u u u u u u u u u u u u u u u vv {uU "-- * "#-$*)"*) u u u u u u u u u u u u u u u u u u u u u u u vw {u X ")'. *+ *'$-$*)"($ u u u u u u u u u u u u u u u u u u u u u u wv { uXuY (#) *+ *'$-$*)"($ u u u u u u u u u u u u u u u u u u ww {uXu U  '$'" *'$-$*)"($ u u u u u u u u u u u u u u u u u u u yU h ‘Oe^QLtOaTP ’€ j “T P~PeSOa _aeSQPsa …€ € ‘”OQ^SSO •^s^NO qfh ’ RadO_P qf €

kl™šmžŸnšlp

 ¡  ¢

@>£>¤B¥ F; @;D<@D¥

!" &&)"   '$'" '* $")" ." '-$ '& (" &+$))" *$ $ (" |"(#x

)" *$  #*  )$-" &$ (" +$) *$ $((" ,"$  ¦§¨© ª«¬­®¯°±© #* )$ "- HI # #*" + +( "  '-&#)$ $ '")" "((z#) ( )Ž '-&#) *+u ²³´  µ
¶´
 "( '#-$*) *  "($ & "- $#-$$ ($ $+#$*) *,-" * J Yu ! )$"-  HI '.$ " |"* "(  )$-" |$*+* *$ ) * #*z#* '" )#))#" ") u

Uu  HI '.$ &$|$*+* *  ) & I")'.u  &* $$$ $‚#$*x

 "(  -#() ).$"u

Xu $ HI '.$ |$*+* "''$))") '*' "-J ($  $  '# *$'$ x

)"*· ( +"  &""(($( -· ($ ( '$*$ '.$ "&& "- $|* $$

&$$*) · ") *$'$" $ (" ( ('" *$· #*" ) -" $((" #")"

$((z *)$" '-&#)" *$·#* )$- *$ -" - $*) ( ‚#"($ (HI $|$

$$ '*'(# $ $ ( HI &$|$$  -$* (" & I ( )Π &)$ $$

{u (" & "))",-"  '-&#)$  &* I ( Â '-&)" " '$*) *" "  - x

+( " "  -"''. *$  *+($x&'$  %· $)$+$*$$ $ +"* ")$ *

'(#)$u $((" $)$ '.$ *)$'**$))$ * $( '(#)$ "&& "- '.$

." #*" I"" (")$*" $ #* "()" I"*"u ('#*$ '""))$ ) '.$ $ *x

 Ã'-$ ) &  &'$$· ‚#"*) )Œ  -$- "· *#-$  '&# $ ("

&$' ƒ'" I"*" '* '#  '(($+")Ä * *) )") ) '"-$*)$u ()$

'""))$ ) '.$ * *|$'$  *"- '.$J * &") '("$·I") &$*"$ "(($

( '$*$  ) & Å") *+ à Å))"*) Ä '.$ &* $$ &)")$ " #*

* "((z"()u Wu +* *  $ '") * +* --$*) " "( & Æ #* #* ' HIu vu Ç &$| )" (z$ )$*"  #*  )$-"  *) ƒ'" &$ #* * $-$  )$))  $|$*) ‚#"( (z" |  #* *#| HI·(" #" )$- *" *$  "( ( - )$ ( ,"(( -$*)  #* $$'# *$u wu ! '& $(( '.$#($  "(('"$ HI * " | -" - "* "('#*$ ,#* * I $)) |  +#""*) "('#*$ - #$ $(($ &$,-"*'$ $((z *x

)$ '.$#($u  &$ "' ") " ' "'#*" - #" &)"** -&"))"$

*$(($ $'  * &$$ "(( '.$#($u

 ¡È É

9¥:;¤; F<: £@>Ê:<Ë¥

!z$&  *$ $( &I($-" -$))$ * $| $*" "('#* &#*) ' ) '  +#""*)

(zI $)) | '.$ * )") &$ƒ") u **"* )#)) & "- $|"$ --$x

 ")"-$*)$ '.$ ' )| "- "|"*) " #* &I($-"  ) & ª©§¯¦¯°±­¬© +#"x

"*)$ (z "(('" *$ )) -"($  #* * $-$   $ ( - )")$ * #*  )$-" 

) & Ì© ­¬Íίϩu

$*)$ " #* (") ( &I($-" $((z "*"(  $((" +$) *$ )) - ")" 

 $ "&&") $*$ " #*"'("$ &I($-  "()"'-&($ )Œ·"((z"()"&")$

)|"*' * #*  )$-" $"(x) -$·$ ‚# * '* )$-& ) '.$ I$* $)$- *")$

$ | *'("*) ** & "- #"$ "(+ )- )&& &$"*) &$ ** *)#$

!"  )#" *$  "*' & Æ '-&( '")" $ &$* "- '.$ | *'( #(($ '"x $*$ $  *+( HI * ( #* $+( "&$)) " )$*$  '*) *$(("  '$'"  #*" (# *$u  $ |"** "Ô"*'")$ "() "(+ )- &$ *  "$ (" '$()" $ HI |$ (" - +(  (# *$· *$( )$*)") |  *'$-$*)"$ ( & Æ & I ($ ($ - #$ ' )")$ * &$'$$*"u $ ‚#"*)  +#"" (z"&$)) $( $"(x) -$  "-  ,*)$ "( '" & Æ

'-&( '") |$ )"Õ " $$+# $ ** * &$  ' -" ' &** "

)"*$  HI  |$ ," ( "' ") " $|$*) " *'* Ã'-$ " $$-& 

( ( " |  #* $|$*)#"($ ,"(( -$*) #"*)$ (z$$'# *$Äu

Ö×Ø×Ö

´ÙÚ Û´


Ü* &I($-" $'  *"($ Â #* &I($-" * '# #*  & Æ $'   )|"*

" |$ $Ý$))#"$ $(($ '$()$ ,"  |$$ "()$*") |$·  &$)) " $)$- *")

I $)) | u

!" Þ¯§©Ì§ ­ ßà©Ì­Î¯á­  #*"  ' &( *" $(") |"-$*)$ $'$*)$u ( )$- *$

 '$'" &$") |"  )") '* ") |$ (" ƒ*$ $+( "** âXV $ $ |" "(

)$- *$ *+($$ ßà©Ì­Î¯°±­¬ Þ©¦© ­Ì§¨  ßà©Ì­Î¯°±¦ Þ©¦© ­Ì§¨ * "-$ '"*u

!"  '$'" &$") |" Â #*"  ' &( *" '.$ )"))" $(( | (#&& $ $((z "&x

&( '" *$  -$) ' $*) ƒ' &$ (" (# *$  &I($-  $'  *$ '.$ 

&$$*)"* * -()$&( ' $  |$ $)) $((" | )" $"($u % )"))"  '$+( $$

‚#"( $'  * &$*$$ &$ +$) $ *$( - & â # $Ô' $*)$ #*  )$-" $"($

#) ( "* )#-$*) -")$-") ' 㠂# * ( '& $(("  '$'" &$") |" Â

‚#$((  ,* $ #*" I"$ ' $*) ƒ'" &$ '$'"$  "*"( "$ $ '-&$*$x

$  )#" * "*'.$ '* )#))#$ -() '-&($$ $ ‚# * #) ( "$ ‚#$)$

*,-" * &$ &$ $ ( '-&)"-$*)  #*  )$-" $ &$ - +( "$ ($

&$)" * $(  )$-" )$u

!" *$'$ )Œ  #* "&&''  ‚#"*) )") | " &I($-  $'  *$  ("x

+"-$*)$  '*' #) * -()  - $)) $((" | )" $"($ $ * &") '("x

$ *$ &I($-  $'  *$ '.$  &$$*)"* *$((" +$) *$ $  )$- 

&# *$ $ *$((" +$) *$ z -&$"u

!" *$'$ )Π$((z# $ -$) $(("  '$'" &$") |" "((z *)$* 

& Æ  '*' #)" '* #*" $-&$ -"++ $ $ "& " $&"* *$ $(($ "$$ 

& I ($ "&&( '" *$u * &") '("$· +( "-I )  -"++ $ | (#&& $(x

(z"&&( '" *$  '$'" &$") |"  +#""* &I($- -"*"+$ "( · &I($

-+$) *"( ·&I($-  &+$))" *$u Ü* $$-&  $ &I($- '.$ &*

$$$ "Ý*)") &$ -$ $(("  '$'" &$") |"  "&&#*) ( &I($-" *

"-I ) *#) "($ $((" & "* ƒ'" *$ $((" &# *$ã  )"))"  $)$x

- *"$ ( |$((  &# *$ $ä (z#) ( " *$   $ã  ."** &$

&I($-  "(('" *$ )) -"   $ '  &I($-  +#""*) ("  ) I#x

 *$   $ ( - )")$ )" "()$*") |$ '*'$*) * - " - * - "$

( ') '-&($ |  -" - "$ ( +#""+* ))"($ã )"(  $ &x

* $$$ -")$ $ & -$· -"*&$"· )$-&  ("| # -"''. *$· '"& )"(

*|$) ) u Ö×Ø×Ø Ú åÚ  ¦¯¦Î©Ï¯ Ì© ­¬Íίϩ * ‚#$(( * '# (" '$))$" $(  )$-" **  &$*$ ("-$*)$ "(  #()") (+ ' $((" '-&#)" *$·-" "*'.$ "( --$*) * '# )"($  #()") | $*$ &))æYçu * +$*$$ #*  )$-" $"(x) -$  '(($+") " $($-$*) $( - $"($ $ *$ - )"$ ( '-&)"-$*)ã )"( $($-$*) * " |()$ '(($+") ," ( " | *'(  &$'$$*" $ (" ( $$'# *$ | $*$  &$)#)" * '*) *#" *$

*$((" '$))" $‚#$*"u !z"&$)) & Æ -&)"*)$ $)" '.$ +*#* $ έ¦è

." $ | *'( )$-&"( "  &$))"$ $ '.$ ‚#$)" '""))$ ) '"  &")$

,*"-$*)"($ &$ $( *$"$ ( '-&)"-$*) $((z *)$  )$-"u

 )"Õ &* $$$ '(" ƒ'") '-$ à©Ì¯°ª¯§¯ $ ±°±Íà©Ì¯°ª¯§¯u  &

- +#""*&$" * '.$ |$*+* $$+# )$ ,$‚#$*)$-$*)$· * -$+("$ $ ' '( 'u ( )$-& '.$ *)$'$ ," (z *    #* $$'# *$ $ (" #''$ |"  ')"*)$ $ | $*$ '. "-") à©Ì¯°ª°u Ü*z&$" *$ ±°±Íà©Ì¯°ª¯§­  #*" '-&#)" *$ '.$ +$*$"(-$*)$ | $*$ $$+# )" * &)" $(|$ ƒ'"  #*$|$*) ­¦¯±§Ì°±°u *‚#$)"  )#" *$ * +$*$$  *) ( )$-& - * - '.$ *)$'$ ," #$ $|$*) '*$'#) | u

~SP_Oé_P sPeSaNLQO

!$ ¦à©§¯ê§¨© ΩÏà°Ì­¬¯ $(  )$-" * $ƒ* )$ "))"|$ $ | *'( )$-x

&"( ·)"( | *'( * &$ $ƒ* ) '( )$- *$ ª© ­ª¬¯±© Ã'"$*"Äu Ü*"

$"( *$ | $*$ $ƒ* )"'-$ ()$-& $*) (‚#"($ #*)"Õ $|$ "|$'*'(#

(" && " $$'# *$u

( &I($-"  +""*) $ '.$ )#))$ ($ $"( *$ |$*+"*  &$))")$   #'$

"( '$'"$ #* & "*  '.$#(" *$ $ )"Õ * - )"($ '.$ "*'.$ *$( '"

&$++ $ ($ $"( *$ |$*+"*  &$))")$u  )* "*'.$ "() ) &  | *'(

)$-&"( '-$ (  )" '.$ &#ë *)$'$$ ," ( --$*) * '# #* )"Õ

 &*) &$ $$ '-&#)") $ ( --$*) * '# $Ý$)) |"-$*)$ $*)" *

$$'# *$ Ãϯ±¯Ï«ÏìÏ­í¯Ï«Ï ª©¬­îÄã &&#$ $ | *'( '.$  +#""* ( )$-& -" - '.$ &#ë *)$'$$ ," ( --$*) * '# #* )"Õ '- *' " (" && " $$'# *$ $ ( --$*) * '# $" )$- *" Ãϯ±¯Ï«ÏìÏ­í¯Ï«Ï ©¬­à¦© ª ίϩÄu Ü*  )$-" $"(x) -$ &#ë $$ '(" ƒ'") * "'' '* (z -&)"*" $((" | (" *$  #*" $"( *$u $ $ )* )"* "(-$*)$  )$ ) & J

•

Ü*  )$-"  ) & ¨­Ìª  #* * '#  "(#)"-$*)$ *$'$"  '.$ ($ '-&#)" * |$*+"* $"# )$ $*) ($ $"( *$ &$ƒ")$u !" | x (" *$  #*" &#ë "|$$  &$'# * '")")ƒ'.$ *$(  )$-"  *$( -$(( $"($u

•

* #*  )$-" $ƒ* ) ¦°ïη (z -&)"*" $(  &$)) $(($ $"( *$  $-&$ * & - & "*·-" *,"*+$*$ #*" ** '-&)"  &$'# *

$&""I ( " ƒ* $( '-&)"-$*) ,#)# $(  )$-"u * ‚#$)$

 )#" * #*  )" &#ë $$$ "''$))"I ($ $ "((" $"( *$ ' &*$

& Æ '.$ "() " #*" - #" -$ " $( )$-&   &)" &$)$u

•

$ #() -· * #*  )$-" '(" ƒ'") '-$ ê ÌÏ·&* $$$ *,"*) ''" *"(-$*)$ | *'( )$-&"( -&) · -" ** )" "- *$#* I$*$ƒ'  $ $ "''"$u Ç -&)"*)$ *)"$ '.$ #*  )$-" | $*$ $ƒ* ) ¨­Ìª "*'.$ ("-$*)$

* &$$*"  #* & ''(" & *$  )"Õ '* $"( *$  )"($ ) &· '.$

"( "-I $*) - ) '-&)"* (z *)# *$  #()$  &I($-") '.$u

%&$· * ‚#$)$ '*  * ·  )$- * &+$))") &$ )"))"$ +* )"Õ

"((" )$+#"  #* )"Õ  ) & ."u ð#$) '-&)"-$*) $*$ &|'"

#* |" -$* *"-$*) $(  )$-" $ ( # '*$+#$*)$  +  -$*)u

sP_TO_P OeSQPePTsLsO”P

!z -&($-$*)" *$  #*  )$-"  '-$ ( &+"--"  ""*+ " &$ ,"$

* - '.$ )#))$ ($ &$' ƒ'.$ |$*+"*  ,"))$u #))$ ($ I" $(($ "x '. )$))#$ ,)ñ"$ #")$ *$  )$- $"(x) -$ &* # | $ " "() ( |$(( * ‚#")) '(" u !" '$()"  #*" '$)" "'. )$))#" *Å#$*" ** &' ("  #' )" $ ($ &$,-"*'$ $( *)$  )$-"· ," ($ ‚#")) ,"- +( $ * | #")$ )| "- ‚#$((" '.$ &$|$$ (z©¦©§«®¯°±© §¯§¬¯§ ­ $((z "(+ )-· (z#  àÌ°§©¦¦¯ §°±§°ÌÌ©±Î¯ ")) |") " $|$*) " *'* · ‚#$((" I"")$ #(( ¦§ ­Ïò¯° ª¯ Ï©¦¦­óó¯ $  )$- §¬¯©±Î©Í¦©ÌᩱΩu !" )$'* '"  ©¦©§«®¯°±© §¯§¬¯§ ­ $( &'$  (" )$'* '" & Æ '*( ")" $ -"++ -$*)$  Ý#"· &"))#)) *$  )$- & Æ ")") u !z * $-$ $ )"Õ

" +$) $  &$ƒ") $ )#)) )"Õ *  ) & &$  'u $ )"( 

)$- & I ($ ) ("$ (" '.$#(" *$ '-&($)" $ )"Õ * - " ")) |"$

(z$$'# *$  &$)#)"  +* )"Õ * - ' '( 'u !$ ")) |" * $ |" )"Õ

 "Ô")" "((" +$) *$ )$-& ")" $(($ &$" * * 'u ( & "* $(("

'.$#(" *$ )) ‚#$)$ '*  * &#ë $$ ô&$)"I ( )õ * - )"($

'.$ (" +$) *$ '-&) #* I" |$.$" "( &#*)  | )" $(($  $

"I )$· '-$ '*)&") )"  )$- 'ö &+$))")  #()"* &' *$

" #I $ ""))"-$*) * $+# ) "((" - ƒ'" $((z * $-$ $ )"Õ " +$) $  " ( Å#))#" * * )$- *  )$-& *$'$"  "( ( '-&($)"-$*)u $  )$- '.$ &$|$* (z )$" *$  έ¦è §°±§°ÌÌ©±Î¯ (" * *$ $ HI " $$+# $  *)" " #*x) -$· *()$  *$'$" " "*'.$ (" &$$*"  #*z"+$*)$ ¦§¨© ª«¬­Î°Ì© '.$ &$*" ($ $'  * # '-$ '.$#("$ )"Õ $ x )$*) u * ‚#$)" |  *$ " +* )"Õ | $*$ "' ")" " #*x) -$ #*" &  )Œ

$ ( )"Õ '.$  &)" (" & Æ "()" | $*$ &) * $$'# *$u ( -"++  &x

I($-"  )"($ '.$-" Â ( - " "))"$ &$ +""*) $ (  &$))  )#))$

) $ "))"I ( u * ‚#$) '" (  )$-"  #()" &$ë -() & Æ Å$ I ($ $

""))"I ($ "((" +$) *$  )"Õ "*'.$ **x&$  ' u

 ¡ù

CB¥B> F<::ú¥@B<

 ¡û

=>9?<@A<9B ¤DE<FG:;9A

( §°±á©Ìó©±Î ¦§¨© ª«¬¯±ó æ Uç  )") $") '-$ "(+ )- &$ (" '.$#("x

 *$  )# * # -$* &'$ ,"' ( )"* (z"&&( '" *$  #*"

-() )# *$  | *'( "I )" $ $# ) '.$ &$' ƒ'.$u

!z "(+ )- $( '*|$+$*) '.$#($ Â '-&) " & Æ ," * &$*$*) ·

+*#*" $(($ ‚#"( *  " (z"(+ )- |$ #*" (# *$ '.$  (|$ #*

&") '("$ &I($-"  #* | *'(u

!$ |" $ ," '* | * #*" $-&( '$ *)$,"'' " '.$ &$-$))$  $& x

-$$ #* ( |$((  &$,$$*" &$ (z"(('" *$ &" "($ $ )$-&"($  +*

)# *$u

&&( '"* * #''$ *$ +* $# ) '" ))$* "- "((" ƒ*$ #* & "* 

"(('" *$ $(($ )# * * +"   ,"$ (" -"++  &")$ $ | *'(

'* $") u

! ¦§¨© ª«¬¯±ó $(($ )# * # -$* &'$ )"  |$*)"* #*

&I($-" $-&$ & Æ  Ô' ($ "  (|$$u $((" -"++  &")$ $ '" &"x

) ' $  $*)" *$((" '("$ $ &I($- x'-&($) · $*" '*)"$ '.$

II "- ," ,*)$ " -() | *'( * '*)") ,"  (u

$( '"  &'$ #&$'"(" '*Å )) +* ," #$ "&$)) -x

&)"*) &$ )|"$ #*" I#*" (# *$J (z¯¦ÎÌ«§Î¯°± ¬©á©¬ à­Ì­¬¬©¬¯¦ÏÃ!Ä

$ (" Ì©ó¯¦Î©Ì àÌ©¦¦«Ì©üu

%$‚#$*$  ' '$ '-&)$ " #* & Æ "() +"  &""(($( - &$

*)#'* #*" -"++ $ &$ *$ # $+ ) $( &'$$u $ +$*$"$

#*" I#*" "(('" *$ $(($ )# * #* '.$#($ $|$ -"*)$*$$ ( & Æ

"() +"  &""(($( - & I ($ $*" "#-$*)"$ )&& ( *#-$ 

Ì©ó¯¦Î©Ì ¦à¯¬¬¦u

$('" &  ¦à­Î¯­¬­Ì§¨¯Î©§Î«Ì© +$ #*z "()" '("$  &I($-") '.$ "

$'*" $( ª­Î­ ª©à©±ª©±§©ó̭ਠ'")# ) "() &  &+"--" * $"-$·

" $$-&  "('#*  $ &#'* +"ƒ '""))$ ") " &'. &$'

ýþÿ þþ
 
   

       þþ   
    
      
  
þ
   ÿ   þ               þ     þ    þ 
   þ   
þ  
       
     

 
        þ    
             þ 
 
 
 
     þ      
           þ      
  !! "#$%   þ 
  
     þ         &' !% $%%($%("% 

' ) ' $ ‚# *  ,-" "((#*+")" '.$  &$)"* I$*$ "((z " *$  "('#*$ '("  $# ) '.$ -() $Ô' $*) * ‚#$)$  )#" * · -$*)$ *$( '"  &+"--  ,-" "(("+")"  -"++  -&)"*"- * - "$ (*#-$  '-#* '" * '.$ ') )# '* (" ,*)$  *$Ô' $*" & Æ +"*$u  '*$+#$*" #* ¦§¨© ª«¬©Ì &$ $) )# $ #* I#*  #()") ." I +*   &$  #*" I#*" ‚#"*) )Œ  $# ) '.$u "  *"(-$*)$ #* '.$#($ $|$ "*'.$  (|$$ '*Å )) ," ($ |" $ $# ) '.$ )|"* #* -$) ­ª ¨°§ '.$ &#'" #* I#* '-&-$u Ü* -$) #")   |(+$$ )#)) +( , |$ ("  (# *$ $( &I($-" & Æ $ ã #* $'* -$)  ("|  "Ý*)"$ ($  |$$ ) &(+ $  '*Å )) #*" "((" |()"· -" * ‚#$) '" '")# '* &I($- |#) "((" $‚#$* "( " *$ $(($ $# ) '.$ $ "(,")) '.$ "('#*$ $'  * &$  #(x )"* à̩ϭΫ̩ * ‚#"*) ($ *,-" * "  &  *$  #()"* *'-&($)$ $ &* &)"$ " #*" (# *$ '"$*)$ã *ƒ*$ $ )* '.$#($ '.$ 

&&*+*  $"- *"$ '*)$-&"*$"-$*)$ ( )") $( &I($-" ))

)#)) &#*)  | )"· -"  #()") * ‚#$)"  $ *$ * &'. " '"#"

$((z$($|")" '-&($ )Π$+( "(+ )- '.$ *$ '")# '*u

( §°±á©Ìó©±Î ¦§¨© ª«¬©Ì &$$*)" #* *#| "&&''  "(($ &I($-") '.$

| )$ ,*$* #* -$)  ("| '.$ '*$*)$ (" $ƒ*  *$  #* *#-$

"I )"   $# ) '.$ * &$*$*) u ( '*|$+$*) '.$#($ &$" * & Æ

&" * &$*$*) +*#* $ ‚#"( &$" $'* #*z$# ) '" &$  (|$x

$ #* &$' ƒ' &I($-"u #))$ ($ ," '* | * ," ( #* ¯± ΩÌï

­§§¯­

'-#*$u !z *&#)  (z#)&#)  +* $# ) '" Â "&&$$*)") " #*z * $-$

 &$,$$*$· +*#*"  +#""*)$ (z"(('" *$ &" "($ $ )$-&"($  +*

)# *$u +* ,"$ ("|" &$*$* * *&#) ($ &$,$$*$ "(( )") 'x

$*)$ $ - ƒ'"*($u ! '.$#($ "&&( '" ($ $# ) '.$ * #''$ *$ $ "(("

ƒ*$ ( - '* '# ($ &$,$$*$  *  ) I# )$ * '" (" (# *$ & Æ

*$" "  ,"$ ( & Æ "() *#-$ & I ($  | *'( '* $") u !$

&$,$$*$ * $&$$ '-$ #*" ,#* *$ '.$ -$))$ * ' &*$*" +*

$($-$*) $((z * $-$

istruzione × spazio × tempo

'* #* &$ ,-"* (" Ï­àà­ ª©¬¬© à

Ì©ï

©Ì©±®©u ð#"* ( §°±á©Ìó©±Î ¦§¨© ª«¬©Ì ." )$- *") +*

)# *$ | $*$ "' ")" "(( ¦¬°Î '( &$ & Æ "() '.$ *$ &$' ƒ'" ( §¬«¦Î©Ì

!$ && $)Œ $( §°±á©Ìó©±Î ¦§¨© ª«¬©Ì &$-$))* '-& $$ $'  * *

- §°°à©Ì­Î¯á°& #))) '.$ $'(# |u *,")) (z¯± ΩÌï

­§§¯­'*$*)$ " +*

$# ) '"  $& -$$ #* &&  +"  &$,$$*" &$ ( &$  +* '$(("

$((" Ï­àà­·$*" '.$ *$#*"  $$ &#'" #*" '$()" $|$ I ($ &$ ("

(# *$ ƒ*"($ã "*'.$ & I ($ "&&( '"$ & Æ |()$ #* )$ )) * $-$

 $# ) '.$ | ) ( '-&)"-$*) )$") | $(( '.$#($  #'$* (

&I($-"   *"$ ($ $# ) '.$ $ ‚#"* $$ |$*+* $$+# )$u * #() -·

-" ** " &'· (" )#))#" &&)" Â "()"-$*)$ -#("$ $ $*$ -()

,"' ($ (z *)$+" *$  *#|$ $# ) '.$ &$ (  ,"' -$*)  | *'( **

"*'" '* $") u

 ¡- É

F¥BB¥Ë<9B;

( *) '"   ')" "(( '$*"  &&) $ Â *$'$"  '* $"$

"('#* "&$)) · &$ &)$ ##,# $ $( §°±á©Ìó©±Î ¦§¨© ª«¬©Ìu

$(*) '" HI " $$+# $ &$** (&) $(($ )# * u  )"($

* $-$ **  *)" (" '" *"( )Œ· *()$ $ |" "  *"- '"-$*)$ $$*

))&) "((z " |  *#| HI )) ,-"  )$"-   '. $)$ $ " *)$x

|"((  )$-& '*' #) u ('*)$) &$") | "$ Â "()"-$*)$  *"- '·

$ ** & Æ )") ' '-$ *$( '" $( '-& (")$u . Œ ‚#$) & - ,")) $*x

$  '.  ( )$*)") |  &$'#("$ '$'"*  '.$#("$ HI '* #*" & "* ƒ'" *$ " (#*+" '"$*"u * | )Æ  ‚#$)" '* $" *$ (" Ï­àà­ ª©¬¬© àÌ©ï©Ì©±®© |$Œ '. "'' ")" # #$  -$* * Ã

istruzione × spazio

Ä '$'"* (" - +(  "(('" *$ Ï°Ï©±Î­±© ­ $'(# |"-$*)$ &$ ("  -$* x *$ &" "($· |"( " ƒ* "( |$ ƒ'"  #* $|$*) à #*" $ $  ‚#$) Ä '.$ $*" *$'$"  #* "++ *"-$*)u ))#"(-$*)$ ") * *) &$ $** -& I ($ ( '"('(  ‚#$(($ ) -$ # "('#*$ - #$  +#""*) ") '.$ (z "(+ )- |Œ )")x

)"$ $ # )$-&  *)$" | -$ $ HI· * &$$*" $ ‚#"( &)$--

&$|$$$  &$x *$ $ "*'.$ ($ §°°Ìª¯±­Î© ΩÏà°Ì­¬¯ &$ (" $ƒ*  *$ 

#* & "*  "(('" *$ " (#*+" '"$*"u

$ ‚#"*) *$'$" " *,")) · (z&$" *$  '.$#(" *$· ') )# '$

 I ( )Œ  "|$$ #* & "* |"(  &$ #* ("  )$-& ( & Æ (#*+ & I ($

') )# $II$ *#II "-$*)$ #* |"*)"++ u ('*)"  ‚#$(( '.$ '$'. "-

 #* "(+ )-  I"$ '.$ |Œ ,* $ #*" (# *$ ( ‚#"*) & Æ )) - x

")" *$( - * )$-& & I ($ $ '.$ $| ) &$'. ," ($  $ -"''. *"

)) - "**$ (" +$) *$u

! '.$#($ '.$ ' "&&$) "- " $ƒ* $ |Œ ‚# * &$"$ ( & Æ

& I ($ #* '*)$) ) & Ì© ­¬Î¯Ï©" '"#" $(" *")#" " *'*" $+( $|$*) '.$ ( ")) |$"** $ " '"#" $( ,")) '.$ -()  $ * '""))$ ") " #*" ª© ­ª¬¯±©ævçu 'z *()$ " '* $"$ ( ,")) '.$ '*)" "-$*)$ "((" ,-#(" *$  + *"($ $( &I($-"· ( '*)$) |$ ' )| "- " &$"$   ''  ,-$  | *'( & Æ '-&($$ '.$ $** *$'$" " (z *)# *$  #*" *#|" '("$  $# ) '.$ $ ("  $ƒ*  *$  "('#* -$) &$") | *$((" ,"$ * '# | $*$ $' " (z "' " *$ |$" $ && " ," 0°ò $ Ï­§§¨¯±© ‚#"* (" Ï­àà­ ª©¬¬©àÌ©ï©Ì©±®©  )")" '-&($)")"u $*)$ '( '-& (")$ +* )# *$  $$+# I ($ " +* ©¦©§«Î°Ì© *$( '*)$) $ HI $ )* "*'.$ | *'(  '-&") I ( )Œ ," ($ #$ '("  ++$)) ÃHI $ -"''. *$Äu "( | *'( * '(" ƒ'"I ( * #$ ) & J ¦Î­Î¯§¯

$ ª¯±­Ï¯§¯u $((" '")$+ " $ | *'( )") ' Ã& Æ ,"' ( " +$) $Ä * &$x

$*) )#)) ‚#$ | *'( (" '#  ,"' I ( )Œ·'-$ #++$ '$ (" &"(" )$x " Ã)") ' Ä· +#"" '""))$ ) '.$ &$-"*$*) à "(-$* --$*)"*$"-$*)$Ä $ HI $ $( &"' -"''. *$J #* $$-&   (" '*ƒ+#" *$ ."ñ"$ $((" -"''. *" $ $‚#  )  '. $) "( HI * "))$"u $((" '("$ $ | *'( )"x ) '  '"* &#$ ‚#$(($ '""))$ ) '.$ '-$ " $$-&  ( '" '  ("| " '#  ))&)" (" -"''. *" '.$ '. ""-$*)$  ++$))" " |" " * *$(

)$-& -" '.$ " ƒ* $(("  *+(" '-&#)" *$ &#ë $$$ &$ '-$ #*"

- #" ƒ"· '  $ |"*)$ " #*"  ($|" *$ )"*)"*$" ,"))" #(( )")

$((" -"''. *" * $"-$u

%)) (z"&&$((") |   *"- ' *)$* "- *|$'$ ‚#$ | *'( '.$ |" "*

 *"- '"-$*)$ (" ( ,-" -"* " -"* '.$ (" (# *$ | $*$ ')# )"u

"($ ) &(+ "  | *'(· & Æ  Ô' ($ " +$) $· $ |" "((" &$$*" 

"('#* ) &   $ '.$ * " '* $" '-$ #*"  " ô'*#-"I ($õ

" ƒ* $((z"(('" *$ $ HIu 1 *'(  )"($) & * ') )# ) "(($ ( '$*$ã

& -$ * ‚#$(($ ( '$*$ '.$   $* ')"*)$-$*)$ # #*" -"''. *" $ **

&)$* $$$ ' $ " $"· *$ ') )# '* #*" &")$ *)$+"*)$ $ ‚# *

#*" '""))$ ) '" &""+*"I ($ " #* $‚#  ) ."ñ"$ Â# * #* | *'(

$( ) & &$'$$*)$J ¦Î­Î¯§°Äã ($ $'*$ * *|$'$ $ƒ* )$ Å))"*) &$'.3

"( '*)"  &* $$$ &)")$ " #*" -"''. *" "((z"()" Ã" &")) '.$ ("

-"''. *"  ƒ $‚#  )  '. $) "((" ( '$*" *$( '" *$ "II "Ä $ ‚# *

** &* $$$ )"))")$ "(( )$ - $(($ &$'$$*) u * $*)"-I$

'" (" &$'#( " )Π )"($  " $)" $-&$ ( ,"))  $$  &* I ($ *

‚#"*) )Œ ( - )")" $ *$( &$++ $ $ '" *,$ $ "( ,"II +*u

*,")) · * ‚#$) '" · ** "&&$*" #* HI  "&&& " $(   ))  #"$

#*" ( '$*"· ("  &* I ( )Œ  #$))" ( '$*"  - *# '$ ƒ* "( &#*) *

'#  |$*)" *"''$ I ($· *$ $ |" ‚# * '.$ (" +$) *$ $((z "$+*"-$*)

 #*" ( '$*" " #* &$' ƒ' HI ** &#ë $$ ("' ")" "( '" &$ **

 '"$$ * '"  (# *  '"" ‚#"( )Œ  "  ))#" *'* )$*) $·

")) |"* )&& HI· | ( "- | *'( -&) u *()$· #&&*$* '.$

"*'.$ ($ ( '$*$ "II "* $ $‚#  ) '.$ ($ -"''. *$ # '# |$"** ")) |")$

$|*  &$))"$· |$*+* ( - )")$ #()$ -$*)$ ($ & I ( )Œ  "' "$

n™š›š 4

5žn6™no7p

!z"(+ )- $( §°±á©Ìó©±Î ¦§¨© ª«¬©Ì ." #* ,#* *"-$*) '-&* I ($ *

#*" #''$ *$  &"  *") ,"  ( '-$ +( )"  #* & &$( *$u

MATCHING

CLUSTERING

HEURISTICS

heuristic A

heuristic B

heuristic ...

MKP

 +#" UuYJ %'.$-" $((" '-&#)" *$ $(( '.$#($u *'.$ +*  *+( )" · "( # *)$*·  $'-&* I ($ * #*" $ $  *")"  &'$#$J ‚#$) "&$))  -"++ -$*)$ $| $*)$ *$((" ,"$ 

"&&$$*)"*)$ ( &"  $(($ & I ( "' " * ," HI $ ($ -"''. *$·

) - "- &$ +* '&& "  $($-$*) #* ૱Ωóó¯° $‚# |"($*)$ "( |"($ "+x

+ #*) " ‚#$)z#() -" * #*" & I ($ (# *$ ƒ*"($u  ‚#$) ƒ*$ ("

-") '$·'.$ ,#*+$ " *)$,"'' "·"))"|$" $ | $*$ - ƒ'")" "(($ $# ) x

'.$·+*#*" $(($ ‚#"(  $ƒ* )" &$ )) - "$ #* "&$)) $( &I($-" 

'.$#( *+u

ð#"* ($ - ƒ'.$ #((" -") '$ * '*'(#$· HI |$*+* "++#&x

&") * §¬«¦Î©Ì¦ &$ & &""$ " #*" ,"$ '.$ $($ *$Œ #* )) * $-$ 

$ )"))$*$*( $ $'#)"*( "((" -") '$ * I"$ "( *#-$ ( - )") 

( '$*$  &* I ( u

!" -") '$ '-&($)")" | $*$ $("I")" " #* "(+ )-  ϭΧ¨¯±ó "(

ƒ*$  $)"&("*$ (z"''&& "-$*) & Æ |"*)"++  & I ($ "))"|$ ("

$($ *$ $ # $($-$*) u È¡  8 <¥F:;9< ³Ú $ HI " '.$#("$ "&& "- '.$ " |"* '* ,$‚#$*" '"#"($ ** *)" $ &$ +*#*  $  $ƒ* )" #*" '"$*" Ã$"( *$Ä '.$ * '" (--$*) $*) ( ‚#"($ ( HI

j

$|$ $$$ '-&($)")J )"($ ") Â '*$|") *$((" |" "I ($ '. "-")"

deadline

j

ã *()$ HI &$|$* (" & I ( )Œ  $$

&$ * '"  *$'$ )Œ·" $$-&  &$'.3 #I$*)" #* "()HI  )$*#)

& Æ -&)"*)$u $ +* HI

j

 *)" #*" ) -" $( # )$-&  '-&($)"-$*) * '")" '*

estimated

j

u *$$*)$-$*)$ "((" ) -" $( # )$-&  '-&($)"-$*)· &$ +*

j

)$* "- "++ *")" #*" |" "I ($ $"($· * '")" '*

progress

j

'.$ $*)" ( )")  "|"*"-$*) "++ #*) "

j

ã

progress

j

 $ƒ* )" *$( "*+$  |"( '-&$ " V " YJ ‚#"* ( # |"($  #+#"($ " $ |#(  $ '.$ ( HI $|$ "*'" *  "$ (" && " $$'# *$· $ |"($ #* "(("

j

 )$- *")u ( '*)$) $"($ "$II$ ‚#$(( * '# +* HI  * +"  *)$,"'' " ô" .'õ '* ( '.$#(")$· '  ,$ * +"  -"*)$*$$ "++ *") (|"($ $((" |" "I ($ * - " $| )"$ -&$'  *

 |"(#)" *$ã * "$*"  ' ë & "- ) -"$ ( )")  "|"*"-$*) 

#* HI

j

* ‚#"( " --$*)· "&&)"* ( )$-& '.$ $ ." &"") * $$'# *$ '( ") ,* ) "((" |" "I ($

estimated

j

u

*ƒ*$  "- " '*'$*" $((" I"*"  '-#* '" *$ $((" $)$ '.$

'(($+" ($ -"''. *$ $((z *)$ &"'u ð#$)" - #" Â "&&$$*)")" "(

&""-$)

banda

$  $&$" '-$ ( "&&) ," #$ #* )Œ  - #" "I )" $ $((" ª¯Ï©±¦¯°±© ª©¯ ª­Î¯ # ΩÏà°u ´
 ÚÛ9
å
³

 %#((" I"$ $(($ *,-" * -$* *")$·. '$'")  $("I"$ #*z$# ) '" )"($·" ," ö '.$ ($  *+($ ª© ­ª¬¯±©$(") |$ " +* HI |$* $  &$))")$u $ ,"$ '  (z$# ) '" '$'"  "$ (" &$'$$*" " ‚#$ HI '.$ '* (  '.   ** )$- *"$ $*) ("  &$)) |" '"$*"u $ $*$' '*) $(  '.  '.$ '$ #* HI  ** )$- *"$ *$ )$-& $ $") · "*$- " $"- *"$ ($ *,-" * * *) &$ "( ƒ*$  $)"&("$ $ ") #) ( " )"I ( $ #*  *$  &$'$$*" ," HI '*'$*) "( ƒ*$  "$+*"$ $ &#*)$++ *$ "(( '&u $ & -" '"· ''$ ) -"$ ( )$-& "*'" *$'$"  "( HI

j

&$ '*'(#$ · * $(" *$ "( # )")  "|"*"-$*) '$*)$u %#((" I"$ $(($ |" "I (

progress

j

$

estimated

j

· *$ ))$* "- #*" *#|"· * '")" '*

remaining

j

· '.$ $*)" (" ) -" $( )$-& '.$

j

$|$ "*'" &""$ * $$'# *$ &$ )$- *"$ $ '.$ | $*$ '"('(")" '-$

remaining

j

= estimated

j

· (1 − progress

j

)

|$· $

progress

j

 (" &$'$*)#"($ '-&($)")" 

j

· "(("

1 − progress

j

* '" (" ," *$ 

j

"*'" " '-&($)"$u *()$ "((" $ƒ*  *$ 

remaining

j

$ |" "*'.$ (" ) -" $( --$*) * '#

j

)$- *$Œ· ' Â

term

j

|$

now

* '" ( --$*) '$*)$· ' Â ( --$*) * '# ( '.$#($ $Ý$)#" (" ) -" $ )$-& u

$ '"('( "- ( )$-& "*'" "  &  *$ & -" '.$ (" $"( *$

 #* HI

j

 |$ ƒ'. · '"('( "- ' Â

deadline

j

− now

u & '.3 & "x - )"I ( $ $ ( HI

j

 & Æ  -$* *  )"· |"(#)"* (  #()") $(("  Ý$$*" ,"

remaining

j

$ ( )$-& "*'"  &* I ($u !" *#|" |" "I ($  #()"*)$· $*- *")"

delay

j

·  $ƒ* )" ,-"(-$*)$ '-$

delay

j

= remaining

j

− (deadline

j

− now)

!" |" "I ($

delay

j

"#-$ |"( ±©ó­Î¯á¯ ƒ*'.3 ( )$-& "  &  *$

 -"++ $ $( )$-& '.$ $Ý$)) |"-$*)$ ''$ &$ )$- *"$

j

u * ‚#$) '" ("  )#" *$ **  ' ) '"&&  &$'.3$$*

remaining

j

<

deadline

j

− now

"((" |#(  $ '.$ ( )$-&  '#

j

." I +*  - *x $  '.$ ."  &* I ($· * "()$ &"($ &$|$ "- '.$ (" #" )$- *" *$

"||$*+" & -" $((" #" $"( *$· '  *$(("  )#" *$

term

j

≤ deadline

j

u %$ "( '*)"  ))$* "- #* |"($

delay

j

à°¦¯Î¯á°· "(("  "- * $,x

,$)) |  )"  &$)) "(($ ) -$ '"('(")$ $ &I"I (-$*)$· $ $$ |$"x

*  &$))")$·

j

)$- *$Œ *  )"· |"($ "  $ & (" $"( *$ ƒ")" Ã

term

j

> deadline

j

Äu #*‚#$ "))"|$ (z *)$&$)" *$ $( |"($ 

delay

j

·& "- '"& $ ("  )#" *$  +* HI

j

*$( ,"*+$*)$ $(($ $"( *$· ‚# * ")) I# $ $ &#*)$++ " ' "'#* HI

j

*$((" -") '$ $(($ &$,$$*$

P

u $ '"('("$ ( &#*)$++  

j

· '.$ * '.$$- '-$ (" ‚#"*) )Œ

score

j

· # "- #*" ,#* *$ '.$ ' &$-$))"  ))$*$$ #* |"($ *)$* " #*

'$) "*+$ $ '*)$-&"*$"-$*)$ &$ ( & Æ && *"($ "( |"($

delay

j

u *,")) · -"++ $  (  )" ) -") &$ #* HI· )"*) & Æ "()" "Œ (" #" &  )Œ $ ‚# * (z *'$-$*) '.$ ))$Œ *$  &$)) | |"( *

P

u *()$ |$-- '.$ (" ,#* *$  " '*) *#"· ( - )")" #&$ -$*)$

* - " &)$ )$*$$ )) '*)(( ( -" - &#*)$++  $& - I ($

"((z$# ) '" $ "*'.$ ( - )")" *,$ -$*)$ " #*" +( " - * -" Ã|"($

 +( " -"++ $  $Ä &$ $| )"$  "|$$ |"( *$+") | *$((" -") '$u

*ƒ*$ (" ,#* *$ Ã'.$ * '.$$- '*

( |"($ $((" +( " - * -" &$ ‚#$ HI Ï°¬Î° * "*) ' &  &$)) "(("

( '"$*"· ( -" - &$ ‚#$(( '.$ -" &$|$ "- '"$$ ()$ ("

 &$)) |" $"( *$ $ && *"($ "

delay

j

&$ $)"*) HI·‚#$(( '.$ ' · $ "(('") '$))"-$*)$·+ #*+$"** "( )$- *$ * )$-&u ( |"($  Ï°¬Î° ' )") & -"· ( & "- - #"$ *)#'$* #* &""-$) Ã'. "- "-(

δ

j

Ä '"('(") &$ +* HI

j

" &") $ "( # |"($

remaining

j

u Ü*" |()" * | #") )"($ |"($·&$ +*

j

· $

term

j

"#-$ |"( *,$ 

δ

j

"(("

score

j

$|$ $$$ - * -u $ƒ* "-

δ

j

 '"*' '.$ $

remaining

j

* '" ( )$-& *$'$"  "

j

&$ '*'(#$ · "((" ' ë |#(  $ '.$

deadline

j

− remaining

j

* '" (z#() - --$*) I#*  &* I ($ &$ ," *  "$ (" ,"$ '*'(# |" $((" '-&#)" *$ 

j

$ ,"( )$- *"$ * '*'- )"*" '* (" #" $"( *$u $*$* '*) $(($ & I ( Å#))#" * '.$ )$-& -$ &* #I $

 &$)) "((" $"()Œ· ** $ƒ* $-

δ

j

'-$

deadline

j

− remaining

j

· Ã'.$

"II "- $)) $$$ )&&  '. Ä -" '-$

δ

j

= deadline

j

− φ · remaining

j

' Â '-$ #* --$*) "*)$ $ "

deadline

j

 #*" ‚#"*) )Œ  )$-& Ã

φ · remaining

j

Ä &" " #* -#() &( $( )$-& - * - ''$*)$ "

j

&$ )$- *"$ *$(  &$)) $( &&  | *'(u

!z $"  ,*  ‚#$(("  '*)")"$ $|$*)#"(  )" -&$| ) *$(x (z$$'# *$ 

j

|") -"* (z *,-" *$ ")" "

remaining

j

$ ‚# *x  '* $"* '-$ #() - --$*) |"(   &* I ($ &$ ," $$+# $ $ '*'(#$$ (HI· (--$*) * '") "

δ

j

$ ** "

deadline

j

−remaining

j

u " '.$ "II "- )#)) +( $($-$*) & "- $ƒ* $ (" ,#* *$

γ()

à UuYÄ

score

j

= γ(term

j

) =



















min

$

term

j

≤ δ

j

·

α · (term

j

− δ

j

) + min

$

δ

j

< term

j

< deadline

j

·

max

$

term

j

≥ deadline

j

u |$

0

20

40

60

80

100

linea temporale

now

deadline

term

remaining

delay (negativo)

delta

2 * remaining

 +#" UuUJ "&&$$*)" *$ #((" I"" )$-&"($ $(($ +"*$$ * + 'ã

δ

j

Ã$()" * ƒ+#"Ä | $*$ '"('(") &$*$*

φ

: Uu

(δ

j

, 0)

$

(min, max)

· |$

max

 ( ( - )$ #&$ $ $((" $((" ,#* *$ $

min

‚#$(( *,$ $u ( '$Ô' $*)$ "*+("$

α

| $*$ '"('(") '-$

α =

max − min

φ · remaining

j

ð# * (" ,#* *$

γ()

 '""))$ ")" " )$  ) *)$ $))$ Ã|$$$ "*'.$ ƒ+#" Uu XÄ '.$ "$-& * "(($ &$+") |$  '. $)$J

•

HI '.$ ."** &$|$ "-  &"* '-&($)"$ '* ("+ "*) ' &  &$)) "((" ( $"( *$·  '#)* #* I" &#*)$++ · ' Â

min

à "- *$(("  )#" *$

term

j

≤ δ

j

Ä

•

" HI·(" '# )$- *" *$ |$*+" &$| )" *$((z *)$|"((  |"( '* x $") *)$$"*) · &$** #* &#*)$++  && *"($ "( ( +"

  '.  )Œ $ƒ* ) "

delay

j

Ã

δ

j

< term

j

< deadline

j

· '"  ƒ+#" Uu XÄ

•

*ƒ*$ " HI '.$ -" '* $ "- ,# )$-& ( - )$ "' "- ( &#*)$++ 

max

Ã

term

j

≥ deadline

j

Ä Ü*" |()" '"('(") ( |"($ 

γ(delay

j

)

( # "- &$ *'$-$*)"$ |"( #(("  +"

j

x$ -" $((" -") '$ *$( '" * '# '* $" - )#))$ ($ -"''. *$ $(( )$ ( |$(( &$)" *"($u

now

deadline

remaining

delay(<0)

delta

0

max

delay

estimated term

delay

score = gamma(delay)

score

gamma()

delay(>0)

min

phi * remaining

 +#" UuXJ "Ô+#" *$ $((z"*"-$*) $((" ,#* *$

γ()

J $|"$ '-$

δ

*' $ *$((" $ƒ*  *$ 

γ()

*Å#$*"**$ ('$Ô' $*)$ "*+("$ Ã

alpha

Ä *$( )")) *)$-$  $((" ,#* *$ $  '*$+#$*" $)$- * ( '-&x )"-$*) $((z$# ) '"· - ƒ'"*( " $'*" $( HI '.$ $|$ |"(#)"$· *()$

deadline

j

' &*$ "((z + *$ $+( " $((" ,#* *$u ´
 ÚÛ9
å ³



-$ "''$**") (z$# ) '" &$ ($ $"( *$ &&)"· ")) I# '$ " +* HI

#* |"($ '.$  I"" ("-$*)$ #(($ ) -$ $ )$-& *) · $*" '* $x "$ ($ '""))$ ) '.$ $((" -"''. *" #((" ‚#"($ ( ) "- |"(#)"* $·  '*$+#$*"· '-$ ‚#$)z#() -$ &"* *Å# $ #(($ ) -$ $ )$-& )$ u $ |"(#)"$ ($ &$)" * $(($  *+($ -"''. *$ * $(" *$ " HI '* '# &$"*· & "- "' "$ " ' "'#*" -"''. *"

m

#* &#*)$++ · * x '") '*

bm

m

·$ƒ* ) "((z *)$*  #*" '"("  |"( *)" $ *|$"-$*)$

&& *"($ "( )$-&  '-&($)"-$*)  ($|") &$ #*" # )$  HI  x

- ( " ‚#$(( '.$ )")) "-J ‚# * " - +(  &$,-"*'$ ' &*$Œ #*

&#*)$++  & Æ $($|") Â#$) &#*)$++ *$'$" &* $$$  '"|") )"x

) ) '"-$*)$ "(( ) ' $(($ $("I" * "||$*#)$· &&#$ &ƒ(") "

 #()")  #* *#| I$*'.-"ÕÄu

((" (#'$  ‚#$) *#| "&$))· (" |" "I ($

estimated

j

)$-&  '-&($)"-$*) ) -") &$ ( HI

j

·  #()" $$$ #*z *,-" x *$ )&& "&& -") |"u "*'" *,")) #*" ¦Î¯Ï­ $(($ &$,-"*'$ $(("

Ï­§§¨¯±­ &$" '-$  ,$ -$*) &$$)$- *"$ ()$-&

estimated

j

J $*"  ‚#$)"·

estimated

j

." &' |"($ * ‚#"*) **   &$ $ #*z *,-"x  *$ '.$ ' &$-$))"  ,"$ "('#*" &$|  *$ "Ô"I ($ #(($ "()$ -"''. *$ $( &"'u |$* '*,*)"$ * $+# ) (|"($

bm

m

 +* -"''. *"

m ∈ M

'* (" ) -" $(($ &$,-"*'$ $((" -"''. *"'* '# Â )") '"('(")

estimated

j



j

·  ||  '.$ "*'.$ ‚#$)z#() - $II" $$ $ƒ* ) *$((" )$" '"("  |"( 

bm

m

u $( '" &") '·** &)$* &$)$*$$ +* |()" #* &ƒ($

$(HI· & "-  ,$ ' " #* ") '"('(") )") ) '"-$*)$u !"  )#" *$ '"-I " &$ (" |"(#)" *$ $((" |" "I ($

remaining

j

· '.$  ' ) -" ( )$-& *$'$"  "( HI

j

&$ '*'(#$ " &") $ "(( )")  "|"*"-$*) "))#"($u *)$+"* ($ *#|$ *,-" * "  & x  *$ - ƒ'. "- (" ,-#(" &$'$$*)$ 

remaining

j

-() &( '"*(" &$

( "&&) ," ( &#*)$++  $((" -"''. *"

¯

m

$ ‚#$(( $((" -"''. *"

m

* $"-$· ' Â

ÃUuUÄ

remaining

j,m

= estimated

j

· (1 − progress

j

)

|

{z

}

remaining

j

·

bm

j

bm

m

|$

bm

j

* '" ( &#*)$++  "' ") "((" |" "I ($

estimated

j

$( HI

j

u $| "- '.$ (" ) -"

remaining

j

'.$ & -" $" * &$*$*)$ "((" -"''. *" "$ Â &""-$) '"*$ |"( 

j

$

m

·'   &$*$*)$ "*'.$ "((" -"''. *" # '# ) "- ,"'$* (" |"(#)" *$u *$+#$*)$-$*)$ II "-  $ƒ* $ "*'.$ ($ "()$ +"*$$ *)$$")$

delay

j,m

= remaining

j,m

− deadline

j

+ now

term

j,m

= now + remaining

j,m

δ

j,m

= deadline

j

− φ · remaining

j,m

score

j,m

= γ(delay

j,m

) γ

$ƒ* )" $|$* 

 &$* "- (" $ƒ*  *$ 

score

j,m

$|"* '.$ ( # |"($  $ƒx

* ) *$((z *)$|"(( '-&$ ," |"(

min

$

max

u $" #*" '&& "

(j, m)

· ( |"($ 

score

j,m

 '$'$*)$ Ã ‚#"*) -$* ** $'$'$*)$Ä "( '$'$$ 

delay

j,m

· ' Â "((z"|| ' *" 

term

j,m

"( |"($ 

deadline

j

㠂#$) )" "  +* ƒ'"$ '.$ )"*) & Æ Â "() ( |"($ 

score

j,m

)"*) & Æ Â  )) ( -"+ *$ '.$  | $ (" )$- *" *$ 

j

"((" #" $"( *$·$ ‚# * & Æ "() (  '.   #* $|$*)#"($ *,"*+ -$*) $( | *'( " '"#"  $|$*) $)$*  ))) -$u *|$'$ ( |"($ $ƒ* ) '-$

max − score

j,m

·' Â ( '-&($-$*) "

max



score

j,m

·&#ë $$$ '* $") #* * '$ $((z­±Î¯§¯à° §°± §«¯ ΩÌϯ±¯­Ï° ¯¬0°ò0 ¦©¬° ©¦©ó«¯­Ï°¦«¬¬­Ï­§§¨¯±­Ï·'  $(|"($ 

deadline

j

−term

j

u ð# * &$ +* -"''. *"

m

$ &$ +* HI

j

(" |" "I ($

score

j,m

$*)"· * #*" '"("  |"( '-&$ )"

min

$

max

· (  )" Ã& ) |  *$+") | '.$ $  "Ä -")#"I ($ "(('"*

j

#

m

J $ ‚#$) &#*)$++  #()"* -$x  "-$*)$ "() &$ )#))$ ($ -"''. *$ $( &"'·"((" (HI

j

 $Ý$)) |"-$*)$  "()" &  )Œ  &$)) "+( "() HI $ )$*) u !" |" "I ($

score

c

j,m

$ƒ* )" "&&#*) '-$

max − score

j,m

·' #++$ '$

*|$'$ ‚#"( -"''. *$ '$+( $$ &$ +""*) $ ( & Æ & I ($ '.$

j

ƒ* '" *$ )$-&  '. $) · $) )#$* &$ $$ |"( & Æ "() u

score

m0

m1

m2

max

min

score

max

min

score

c

score

c

 +#" Uu{J "&&$$*)" *$ *)# ) |" $( "&&) ,"

score

j,m

i

$

score

c

j,m

i

&$ #* HI

j

'( &"' -"''. *$ $ƒ* ) "((z * $-$

{m

0

, . . . , m

2

}

u

!z *)$" $# ) '" &$|$$ &$' ë  #) ( "$ (" |" "I ($

score

j,m

&$

'"('("$ #*૱Ωóó¯°'.$  &$''. ("+ #)"&  )Œ" "$+*"$ "

"+( "() HI· '$"* #* &)$) '  *"-$*) &" "($ *$((z * $-$ $ HI $ )$*) u $*- * "-

σ

j

‚#$) &#*)$++  $ $ƒ* "-( '-$

σ

j

=

X

∀m∈M

score

j,m

Ü*" |()" $ƒ* ) ( &#*)$++  *$$*)$ "(HI

j

· (  &") "- #(($ -"'x '. *$ && *"(-$*)$ " |"( '"('(") &$

score

c

j,m

$ "' ") " +* -"''. *"

m

$( &"'u !" ,-#(" '.$ $ƒ* '$ &$+* HI

j

$ &$+* -"''. *"

m

(&#*)$++  '* '# *'$-$*)"$ ' &$)) | $($-$*) $((" -") '$ $(($ &$,$$*$  (" $+#$*)$

σ

j

·

score

c

j,m

P

∀m∈M

score

c

j,m

 ƒ* $((z -&($-$*)" *$ $((z"(+ )- $| "- (" $+#$*)$ #+#"x +( "*"J

X

∀m∈M

score

c

j,m

=

X

∀m∈M

(max − score

j,m

)

= max · |M | −

X

∀m

score

j,m

= max · |M | − σ

j

!z *)$ "(+ )-   &)")  $+# )·' )) * &$# ' '$·(" '-x &($ )Œ  *)" " '(& z''.  $$$ *$((z *$ $(("  -$* *$ $((" -") '$·‚# * (" & Æ I"" & I ($ $  "$)" #

O(nm)

'*

n

 ( *#-$  HI $

m

( *#-$  -"''. *$· ' Â

m = |M |

H

deadline

(max, min, φ)

;

<=> ?@ABC=D

j ∈ J

E = ;

σ

j

= 0

<=>?@AB F@ABGH?

m ∈ M

E = ;

remaining

j,m

= (estimated

j

· (1 − progress

j

)) ·

bm

j

bm

m

term

j,m

= now + remaining

j,m

score

j,m

= γ

φ

(term

j

)

σ

j

+ = score

j,m

score

c

j,m

= max − score

j,m

I

sum = max · |M | − σ

j

<=> ?@AB F@ABGH?

m ∈ M

E =

matrix

j,m

+ = σ

j

· score

c

j,m

· sum

−1

I I '*

J

* '. "- +"*$ (z * $-$ $ HI $ )$*) "((z ")) $((" '-&#)" x *$· '*

M

( &"' -"''. *$ $ '*

p

j,m

(z$($-$*) $(("  +"

j

$ '(**"

m

$((" -") '$ $(($ &$,$$*$ #")" "(($ $# ) '.$·' Â

P

|J|×|M |

u È¡È J9£GB ð#$)" $# ) '" '* $" (" '-&#)" *$ $( +$*$ ' HI

j

*$$*)$-$*)$ "( &I($-"  $|$*)#"( ") '.$ &* $| $ "

j

&$ ," &$+# $ (" #" '-&#)" *u  ") '.$   $* ('"(-$*)$ ** ') )# '*  &$ 3 #*"

,*)$ *)$$"*)$ &$ $Ý$))#"$ "('#*" )) - " *$· ("  )#" *$ '"-I "

‚#"* ‚#$) *  ('") # #*"  & Æ -"''. *$ $( &"'u

ð#$) "&$))   ($|" *)$$"*)$ "( &#*)  | )" $(($ &$,-"*x

'$ $((z *)$  )$-" $ $(  *+( HI· * ‚#"*) ( )",$ -$*) $ ") ·

‚# * (z "&$)) $(($ '-#* '" * ," -"''. *$  |$$· ." #* ') **

)"'#"I ($u !"  )#" *$ &#ë "*'.$ &$++ "$ *$( '" * '# (" ‚#"*) )Œ

 ") '*)$-&"*$"-$*)$ * )"* )· #&$")" #*" '$)" +( "·&)$II$

$+""$ ($ &$)" * $((" $)$ * - *)$(("I ($u

* '*'$* (- *'# #*HI ,#))"+( "'. | $-) · -&#) "-

"( HI #* |$.$" * ,"$  )")#& &" "( )$-& *$'$"  &$ )",$ $

"))"|$ ‚#$)" $# ) '" & "- *#$ (" ,"$  -")'. *+ " -$))$$ *

$$'# *$ (HI #(($ -"''. *$ # '# * &$$*) ") #) ( u

 $'*" $( +"  "''#")$" '.$ |+( "- "++ #*+$$ $ $(($ *x

,-" * '.$ "II "- #((" $)$  *)$'**$ *$ & "- " |"$ "

))$*$$ #* $# ) '" & Æ  -$* $Ô'"'$u $( *) '" ($ *,-" *

 &* I ( ** &$-$))*  -$(("$ #* $# ) '" &") '("-$*)$ ƒ) x

'")"· -" (" #" - ƒ'"· * &$$*"  & Æ ") · ** '-&)" #* ,

+"|J *$((" $'*" &")$ $( &""+",· -)$ë " ) )(  $$-& 

#* "(+ )- & Æ "''#") '.$ &)$II$ ) )# $ ‚#$(( & *' &"($ *$( '"

"|$ - & Æ *,-" * u $ +* HI

j

'*' "- # ‚#"( -"''. *$   $* ª­Î¯ $ (" I"*" $((" $)$  *)$'**$ *$J ‚# * I""*' #( ')  #* $|$*)#"($ )",$ -$*)· )"I ( $- #*" &$,$$*"u % "

transf

)"($ ')· ( &x  "- ) -"$ '-$ ("  -$* *$ $ ") &" # |" * $( &"' Ã

inputsize

j

Ä &$ (z *|$ $((" I"*" $((" $)$ Ã

bnet

Ä· ' Â

transf =

inputsize

j

bnet

* "|$* ") &$' ƒ' #((" I"*" $((" $)$ "#- "- '.$

bnet

 " #*" - #" |"( " &$ ($ I"*" ," +* & I ($ '&& "  -"''. *$ $(

&"'u ð# * &$ +* HI

j

 #Ô' $*)$ '* $"$ (" ‚#"*) )Œ  *&#) *$'$" "

j

$ '(('") # +* -"''. *"

m

$( &"'· &$ $& -$$ #*" &$,$$*" *$((" -") '$ $(($ $# ) '.$u * '. "- '*

input

j,m

(" ‚#"*) )Œ  ") *$'$" "

j

$   $$*) #

m

u $ +* HI

j

· &$ +* -"''. *"

m

· # "- ( "&&) ,"

input

j,m

$

inputsize

j

&$ - ƒ'"$ ( |"($ $(($  *+($ $*)")$ $((" -") '$  +* HIu !" - ƒ'" (" $ƒ* "- '-$

p

j,m

+ = max ·

input

j,m

inputsize

j

'*

inputsize

j

=

X

∀m∈M

input

j,m

'*

p

j,m

(z$($-$*) $(("  +"

j

$ '(**"

m

$((" -") '$ $(($ &$,$$*$

#")" "(($ $# ) '.$·' Â

P

|J|×|M |

$

max

 #*" ')"*)$ $ƒ* )" &""-$) x '"-$*)$ "(( *)$* $((z$# ) '" '.$ )"I ( '$ ( &$ $((z$# ) '"u %$ (" $)$  '**$ *$ ,$ )#))#")" * - )"($ " $*$$  |$$ ($ I"*$  '-#* '" *$ ," #$ +$*$ '.$ -"''. *$·"((" '$++ "- ("

,-#(" &$'$$*)$ ) )#$* ( "&&)

input

j,m

/inputsize

j

'* #*z"()

&& *"($ "()$-& *$'$"  " $*$$  &* I ( # #*"'$)" -"''. *"

m

)#)) ") *$'$" "(HI

j

u  &$* "- (" ,-#("

transf

$ # "-(" &$ $ƒ* $ ( ') * )$- *  )$-& $( )",$ -$*) $ ")

input

j,m

" #*" -"''. *"

m

* #*" -"''. *"

m

0

trasf

m

0

(j, m) = input

_j,m

· bnet

−1

_m,m

₀

|$

bnet

m,m

0

* '" &$ +* '&& "  -"''. *$

(m, m

0

_{6= m)}

(" I"*"  '-#* '" *$ '.$ ($ '(($+"u

|$* #&) '.$ ") &"* $$$ &" "*'.$ # & Æ -"''. *$ $(

&"'

M

· &$ '*'$$ ( )$-& ))"($ *$'$"  &$ )",$ $ ΫÎί ") $(HI

j

# #*" &") '("$ -"''. *"

m

0

·-- "-  #()") $((" ,-#(" &$'$$*)$ '"('(")" &$ +* -"''. *"

m ∈ M

$  |$" "

m

0

u * '. "- '*

transf

m

0

(j)

)"($ )$-& "II "- '.$

transf

m

0

(j) =

X

∀m∈M ∧m6=m

0

transf

m

0

(j, m)

$ '"('("$ (z *'$-$*) $((z$($-$*)

p

j,m

$((" -") '$  "&&( '. -"

(" )$" ,-#(" #")" &$'$$*)$-$*$· #"* #* "&&)   &")  *$

'.$  I"" #( )$-& '.$ ''$ " +* -"''. *" &$ &)"$ * ('"($ )#))

") *$'$" " #* +$*$ 'HI

j

$ ,"|$* ‚#$((" '.$ ." ( )$-& - *$u % "

transf (j) =

X

∀m∈M

transf

m

(j)

"II "-

p

j,m

+ = max · (1 −

transf

m

(j)

σtransf (j)

)

}~PeSOa fKfKq L­¬§°¬° ª©¯à«±Î©óó¯ ­¦¦©ó±­Î¯ ­ §¯­¦§«±­ Ï­§§¨¯±­ ª©¬à­ÌÍ §°à©Ì «± 󩱩̯§°0°ò

j

¦«àà°±©±ª° §¨© M«©¦ÎN«¬Î¯Ï° ¦¯­ §°Ï© ª©¦§Ì¯Îΰ ª­¬ ó Ì­ï ° ¦©ó«©±Î©O ª°á© °ó±¯ ±°ª° Ì­ààÌ©¦©±Î­ «±­ Ï­§§¨¯±­ ¯¬ §«¯ §°¦Î° P ª­Í ΰ ª­¬¬N

input

j,m

O °ó±¯ ­Ì§° «± §°¬¬©ó­Ï©±Î°ïÌ­ ª«© ±°ª¯ ¬­ §«¯ ©Î¯§¨©Îέ P ¬­ ò­±ª­ §¨© §°¬¬©ó­ ¯ ±°ª¯ ­ó¬¯ ©¦Î̩ϯQ

m(0), Input(j,0)=120Mb

m(1), Input(j,1)=80Mb

m(2), Input(j,2)=60Mb

B=120 Mb/s

B=100 Mb/s

B=80 Mb/s

­òò¯­Ï° ¯ ¦©ó«©±Î¯ ̯¦«¬Î­Î¯ à©Ì ¯ á­Ì¯

transf

m

R

transf

m

0

(j) = trasf

m

0

(j, m

1

) + transf

m

0

(j, m

2

) =

= input

j,m

1

/bnet

m

0

,m

1

+ input

j,m

2

/bnet

m

0

,m

2

=

= 80/100 + 60/120 = 1.3

transf

m

1

(j) = transf

m

1

(j, m

0

) + transf

m

1

(j, m

2

) =

= input

j,m

0

/bnet

m

1

,m

0

+ input

j,m

2

/bnet

m

1

,m

2

=

= 120/100 + 60/80 = 1.95

transf

m2

(j) = transf

m

2

(j, m

0

) + transf

m

2

(j, m

1

) =

= Input

j,m

0

/bnet

m

2

,m

0

+ input

j,m

1

/bnet

m

2

,m

1

=

= 80/80 + 120/120 = 2

transf (j) =

2

X

i=0

transf

m

i

(j) = 5.25

¦«àà°±©±ª°

max = 10

O °ÎΩ±¯­Ï° ¯ ¦©ó«©±Î¯ ¯±§Ì©Ï©±Î¯ ±©¬¬­ Ï­Î̯§© ª©¯ ૱Ωóó¯

P

R

p

j,0

+ = max · (1 − transf m

0

(j)/transf (j))

= 10 · (1 − 1.3/5.25) = 7.52

p

j,1

+ = max · (1 − transf m

1

(j)/transf (j))

= 10 · (1 − 1.95/5.25) = 6.28

p

j,2

+ = max · (1 − transf m

2

(j)/transf (j))

È¡ù S ;9;Ë;TT¥T;>9< F<::ú>?<@E<¥F ( ƒ*$  ‚#$)z$# ) '"  ‚#$((  - * - "$ +( &)"-$*)  #* HI "(('"*( '*) *#"-$*)$ # -"''. *$ $-&$  |$$u !zI $)) |  ," ö '.$ (HI  -"*+"")) | #((" )$" -"''. *"# '#  )|" + Œ *$$'# *$· $| )"**$ ( ௱óÍà°±óu ö ,"'$* ))$* "- #* +#""+*  &$)" *

|#) "(  &"-  $(($ ,"  )")#& $ &$* *$  *# HIu

$ "#-$*)"$ (" &I"I ( )Œ '.$ #* HI |$*+" ("' ") * $$'# *$ #((" -"''. *" |$  )|"· '"* "- ($ '&& $

(j, m)

"&&")$*$*) "( -")'. *+ '$*)$ "#-$*)"* ( ' &*$*)$ $($-$*)

p

j,m

$((" -") '$ $(($ &$x ,$$*$ã (" #" '-&($ )Œ  ‚# * #+#"($ "

O(min{m, n})

'*

n

( *#-$  HI $

m

( *#-$  -"''. *$u * '"* '*

score

( &#*)$++  '.$ "++ #*+ "- " +* $($-$*) $(x (" -") '$ $(($ &$,$$*$ &$$*)$ "*'.$ *$( -")'. *+· (z"(+ )- '.$ $$+# "- * ‚#$) '"  ( #''$ | -)")J

H

overhead

(score)

; <=> ?@AB

(j, m) ∈ M atching

E =

p

j,m

+ = score

I È¡û S ;9;Ë;TT¥T;>9< F<::ú¥BB<¤¥ Ë<F;¥

ð#$)" $# ) '"  &$ƒ++$  - * - "$ )$-&   &)" $ HI "

$("I"$u 1($* - * - "$ ( )$-& -$  '.$ *)$'$ ," ( --$*) * '# #* HI

j

" |" Ã

submit

j

Ä $ ‚#"* $ | $*$ )$- *")  "- #*" & x  )Œ -"++ $ " HI '.$ ."** ( - * )$-& $ #  '-&($)"-$*) Ã

remaining

j

Äu -$ *$('" $((z$# ) '" &$($ $"( *$· (|"($$(("|" "I ($

remaining

j

&#ë $$ '-&"") "( "&&) ," ( ")

bm

j

"' ") "( HI

j

$

bm

m

"' ") " +* -"''. *"

m

$( &"'· &&  *$ ÃUu UÄu Ü "- ‚# * ( |"($ 

remaining

j,m