Çoxprosessorlu Planlaşdırma
İki tətbiqetmə çoxprosessorlu bir maşında işləyir. Hər bir tətbiqetmə i (i=1,2) N prosedurdan ibarətdir və bu prosedurlar 1-dən N-ə qədər nömrələnmişdir və ardıcıl olaraq (1,…,N sırasıyla) icra olunmalıdır. Bir prosedur (i,j) cütü ilə müəyyən edilir, burada i=1,2 tətbiqetməni müəyyən edir və 1≤j≤N tətbiqetmə i-nin prosedurlar ardıcıllığında prosedurun indeksini təmsil edir. (i,j) proseduru yalnız maşının P(i,j) prosessorunda icra edilə bilər və icrası D(i,j) saniyə davam edir. Biz iki tətbiqetmənin prosedurlarının maşının prosessorlarında icrasını elə planlaşdırmaq istəyirik ki, son prosedurun icrasının bitdiyi an (hər hansı iki tətbiqetmədən) minimum olsun; bu an makespan adlanır. Biz hesab edirik ki, iki tətbiqetmə 0 zaman anından etibarən planlaşdırma üçün mövcuddur. Planlaşdırma aşağıdakı qaydalara riayət etməlidir:
Bir prosedurun (i,j) icrası P(i,j) prosessorunda başladıqdan sonra, prosedurun icrası bitənə qədər onu dayandıra bilmərik.
Eyni prosessorda eyni zamanda bir neçə proseduru icra edə bilmərik, lakin müxtəlif prosessorlarda paralel olaraq bir neçə proseduru icra edə bilərik.
(i,j) prosedurunun icrası (2≤j≤N) ya (i,j-1) prosedurunun icrasının bitdiyi dəqiq zaman anında tm-də, ya da tm-dən sonra istənilən zaman anında başlaya bilər.
Əgər bir prosedur tm zaman anında icrasına başlayırsa, o zaman icrası tm+D(i,j) zaman anında bitəcəkdir.
İki tətbiqetmənin prosedurları ilə bağlı məlumat verildikdə, minimum makespanı hesablayan bir proqram yazın.
Giriş faylının ilk sətri növbəti təsvir edilən test halları sayını T ehtiva edir. Test halının ilk sətri hər iki tətbiqetməni təşkil edən prosedurların sayı N (1≤N≤300) ehtiva edir. Sonra, birinci tətbiqetməni təsvir edən N sətir gəlir. Bu N sətirin j-ci sətiri iki tam ədəd ehtiva edir, boşluqla ayrılmış: P(1,j) və D(1,j). Bundan sonra, ikinci tətbiqetməni təsvir edən digər N sətir gəlir. Bu N sətirin j-ci sətiri iki tam ədəd ehtiva edir, boşluqla ayrılmış: P(2,j) və D(2,j). Bizdə 1≤P(i,j)≤10 və 1≤D(i,j)≤15000 (i=1,2; 1≤j≤N) var. Diqqət yetirin ki, P(i,j)=P(k,l) ola bilər – bu, (i,j) və (k,l) prosedurlarının üst-üstə düşən zaman intervallarında icra edilə bilməyəcəyini göstərir (həmçinin, əgər i=k olarsa, bu əhəmiyyətli deyil, çünki eyni tətbiqetmənin prosedurları ardıcıl olaraq icra olunmalıdır).
Çıxış faylı dəqiq T sətir ehtiva etməlidir, hər biri bir ədəd – giriş faylındakı müvafiq test üçün minimum makespan. Bu cavablar giriş faylında test halları verildiyi sırada çap edilməlidir (yəni çıxış faylının i-ci sətri giriş faylındakı i-ci test halının cavabını ehtiva edir). Bir giriş/çıxış nümunəsi aşağıda verilmişdir.