ترجمه فارسی عنوان مقاله

کاهش کل زمان تکمیل در یک سیستم کامپیوتری با یک سرور و دو پردازنده ی موازی

عنوان انگلیسی

Total completion time minimization in a computer system with a server and two parallel processors

کد مقاله	سال انتشار	تعداد صفحات مقاله انگلیسی
6118	2005	13 صفحه PDF

منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Computers & Operations Research, Volume 32, Issue 3, March 2005, Pages 599–611

فهرست مطالب ترجمه فارسی

چکیده

کلمات کلیدی

1. مقدمه

2. علامت ها و فرمول ریاضی

2.1. علامت ها

2.2. مدل برنامه نویسی خطی انتگرالی

3. موارد ویژه

3.1. مسئله ی مربوط به (فرمول)

3.2. مسئله ی مربوط به (فرمول)

شکل 1. مثالی که در آن SPT/FAM بهینه نمی باشد.

4. کاهش

شکل 2. زمانبندی S ساخته شده از زمانبندی S’

5. الگوریتم چند جمله ای

شکل 3. مثال پروفایل با h = 1.

6. بسط نتیجه

7. نتیجه گیری

ترجمه کلمات کلیدی

برنامه ریزی - ماشین آلات های موازی - سرور منفرد - مغازه - جریان ترکیبی

کلمات کلیدی انگلیسی

ترجمه چکیده

موضوع مسئله ای که در این مقاله به آن پرداخته شده است، یک سیستم کامپیوتری ساخته شده توسط یک سرور منحصربفرد و دو ماشین موازی مشابه می باشد. فرض شده است که زمان های پردازش در سرور یکانی بوده و هدف، کاهش کل زمان تکمیل می باشد. این مقاله که با برنامه های زمانبندی با یک سرور سر و کار دارد، اینگونه در نظر می گیرد که فعالیت های نصب بطور همزمان نیازمند سرور و ماشین می باشند. در این مقاله، این محدودیت در نظر گرفته نشده و مسئله ی مطالعه شده، استقرار براساس جریان هیبریدی کار با محدودیت نبود وزن بین دو مرحله می باشد. یک الگوریتم که می تواند این مسئله را بصورت بهینه در زمان حل کند مطرح شده است. در نهایت، نشان داده شده است حل این مسئله بصورت بهینه به یک راه حل بهینه برای مسئله ای که بدون محدودیت نبود وزن می باشد، منجر می شود.

ترجمه مقدمه

پردازش موازی توجهات بسیار زیادی را در سال های اخیر، به خاطر بازده خوب، که بخش حیاتی در موفقیت سیستم های کامپیوتری موازی می باشد، به خود جلب کرده است. یک آرایش کلاسیک با یک سرور از فایل هایی که توسط شبکه به مشتری ها لینک شده اند، ساخته شده است. اولین مرحله ی موازی سازی شامل توزیع کد و داده های هر مسئله ای که می تواند موازی سازی شود، به یک مشتری طرح ریزی شده می باشد. برای هر برنامه ای که باید به یک مشتری فرستاده شود، سرور باید با موفقیت کد و داده های روی هارد دیسک را خوانده و آن ها را بوسیله ی شبکه به مشتری بفرستد. در تخمین اولیه، این دو مرحله می توانند بوسیله ی یک عمل روی سرور مدلسازی شوند. این فرضیه افراطی نیست، زیرا در چنین زمینه ای، طراح سعی می کند زمان های پردازش مربوط به مشتری های مختلف را متعادل سازی کند تا بهترین عملکرد اجرای موازی را بدست آورد. سپس برنامه ها و داده ها اغلب اندازه های مشابه داشته و در نتیجه، خواندن و فرستادن آن ها به زمان برابری نیاز دارد. هدف مورد نظر می تواند در صورتی که کاربر منتظر نتیجه ی سریع باشد، کاهش حداکثر زمان تکمیل باشد. اما اگر هدف استفاده از شبکه با بیشترین بازده باشد، هدفی که باید مورد مطالعه قرار گیرد کاهش متوسط زمان تکمیل یا مجموع زمان های تکمیل می باشد. ما یک محیط زمانبندی قطعی با m ماشین موازی مشابه و n کار برای زمانبندی را در نظر می گیریم. هر کار باید بدون جلوگیری از تعیین توسط ماشین پردازش شود. قبل از پردازش، یک کار باید روی ماشین بارگذاری شود. این فعالیت بارگذاری یا فعالیت نصب، بوسیله ی ماشین خاص دیگری به نام سرور انجام می پذیرد. بعد از نصب، سرور دوباره در دسترس قرار می گیرد تا فعالیت بارگذاری دیگری انجام دهد. بارگذاری کار باید بلافاصله بعد از پردازش آن انجام پذیرد. در این محیط، ما اینگونه در نظر می گیریم که زمان های نصب نیازمند یک زمان واحد برای هر کاری می باشند. هدف این مقاله یافتن یک زمانبندی امکانپذیر در یک محیط m = 2 ماشینی، و با حداقل زمان کلی تکمیل می باشد، که مربوط به کاهش کار در فرآیند موجود در شبکه می باشد. بسیاری از نتایج سال های قبلی به مسائل زمانبندی ماشین های موازی با سرور پرداخته اند. کولامانس یک الگوریتم ابتکاری جستجوی پرتو برای محیط استاتیک با دو پردازنده ی موازی و یک سرور منحصربفرد را مطرح می کند که در آن هدف یافتن زمانبندی امکانپذیر است که زمان بیکاری ماشین که حاصل در دسترس نبودن سرور می باشد، را به حداقل می رساند. کراوچنکو و ورنر، هال و همکارانش و براکر و همکارانش نتایج پیچیدگی بسیاری برای این مسائل مطرح کرده اند. گلس و همکارانش مدل های مربوط با ماشین های موازی که برای آن ها کارهایی اختصاص داده شده و نتایج تجزیه و تحلیل الگوریتمی، پیچیدگی و نوآوری را ارائه کرده اند. کراوچنکو و ورنر یک نوآوری برای کاهش مجموع زمان های تکمیل در حالت زمان های واحد طرح ریزی و زمان های دلخواه پردازش پیشنهاد داده اند. با این حال، مسائل بررسی شده در این مقاله ها بطور ضمنی محیط تولید را در نظر می گیرند که در آن سرور می تواند یک اپراتور انسانی، یک روبات یا یک خودروی اتوماتیک راهنمایی شده باشد. در نتیجه فعالیت باردهی معمولا مانند یک عمل چند پردازنده که نیاز به اجرای همزمان ماشین و سرور دارد، در نظر گرفته می شود. در یک سیستم کامپیوتری، سروری که داده ها را به ماشین می فرستد، سرور شبکه نامیده می شود. طی فعالیت باردهی، نیازی به دسترسی به اجرای ماشین وجود ندارد: آن می تواند بک کار دیگر را پردازش کند. در واقع، ماشین ها دارای یک پردازنده ی ارتباطی می باشند که اجازه می دهد آن ها اطلاعات سرور را در هر زمانی دریافت کنند. در نتیجه، در یک سیستم کامپیوتری، فعالیت باردهی می تواند مانند کاری که تنها نیازمند اجرای سرور می باشد، در نظر گرفته شود. سیستم کامپیوتری که ما در نظر می گیریم، می تواند بصورت یک استقرار براساس جریان هیبریدی کار یا کارگاه سیار چندپردازنده با یک مشاین در مرحله ی اول، که سرور می باشد و m ماشین موازی در مرحله ی دوم، بدون محدودیت نبود وزن بین دو مرحله در نظر گرفته شود. این مسائل معروف به NP-سخت بودن حتی برای نسخه ی نسخه ی بازدارنده شان می باشند. ویگنیر و همکارانش، و لین و ژنگ یک بررسی به روز بر روی مسائل زمانبندی استقرار براساس جریان کار هیبریدی پیشنهاد داده اند. با این حال، بیشتر مسائل، زمان کل را بعنوان یک معیار در نظر می گیرند. در حالت کاهش مجموع زمان های تکمیل، پیندو نشان می دهد که امکان یافتن یک راه حل بهینه با استفاده از قانون SPT، زمانی که تمامی عملیات یک کار دارای زمان های پردازشی یکسانی دارند، وجود دارد. متأسفانه، این نتیجه دیگر تحت فرضیه ای که ما در نظر می گیریم دیگر صحت ندارد. در بخش 2، علامت ها معرفی شده و فرمول ریاضی برای مسئله ی کلی داده شده است. در بخش 3، نتایح پیچیدگی و روش های راه حلی برای دو حالت ویژه که در آن ها m = 2 است داده شده است. در بخش 4، ما کاهش چند جمله ای بین مسائل ماشین موازی با سرور و مسائل استقرار براساس جریان کار هیبریدی را ارائه می دهیم. در بخش 5 یک الگوریتم زمانی چند جمله ای برای حل بهینه ی موردی که در آن m = 2 می باشد ارائه شده است. در نهایت، در بخش 6، ما نشان می دهیم که این الگوریتم بهینگی حالت بدون محدودیت نبود وزن را نیز حل می کند.

دانلود رایگان 2 صفحه اول مقاله لاتین (PDF)

پیش نمایش مقاله

چکیده انگلیسی

The context of the problem tackled in this paper is a computer system composed by a single server and two identical parallel machines. The processing times on the server are assumed to be unary and the objective is to minimize the total completion time. The papers dealing with scheduling problems with a server generally consider that the setup activities require simultaneously the server and the machine. In this paper, this constraint is not considered and the studied problem is a two-stage hybrid flow shop with no-wait constraint between the two stages. An algorithm that can solve optimally this problem in View the MathML source time is proposed. Finally, it is shown that solving this problem optimally leads to an optimal solution to the problem without the no-wait constraint.

مقدمه انگلیسی

Parallel processing has received a lot of attention these last years because of its efficiency, which is a crucial part in success of parallel computer systems. Hence, there is a necessity for developing efficient scheduling algorithms in computer systems. A classical configuration is build with one server of files linked with clients by a network [1]. The first step of the parallelization consists in dispatching on a designed client the code and the data of each program that can be parallelized. For each program that has to be sent to a client, the server must, successively, read the code and data on the hard disk and send them to the client by the network. In a first approximation these two steps can be modeled by one task on the server. This assumption is not excessive because in such a context, the designer tries to balance the processing times on different clients to obtain the best performance of the parallelized execution. Then programs and data have often similar sizes and as a consequence, reading and sending them takes similar times. The goal to achieve can be the minimization of the maximum completion time if the user is waiting for fast result. But if the goal is to use the network with the most efficiency, the objective that has to be studied is the minimization of the mean completion time or the sum of completion times.

نتیجه گیری انگلیسی

In this paper, we consider a parallel machine scheduling problem with a server in a computer system, modeled by a two-stage hybrid flow shop scheduling problem with a no-wait constraint. We propose a mathematical formulation for the problem and we propose two polynomial time algorithms for particular cases. We show that the two-stage hybrid flow shop problem is at least as difficult as the parallel machine scheduling problem with a single server. We deduce that the problem under consideration with real processing times is NP-hard. However, with integer processing times, we propose an View the MathML source algorithm that solves the problem optimally. Finally, we show that an optimal solution to the two-stage hybrid flow shop problem with the no-wait constraint is an optimal solution to the problem without the no-wait constraint. The further directions of this work are to consider the problem with m machines, and to consider the communication process between the operation on the server and the corresponding operation on the machine, with more details.