کاهش کل زمان تکمیل در یک سیستم کامپیوتری با یک سرور و دو پردازنده ی موازی
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی|
|6118||2005||13 صفحه PDF||16 صفحه WORD|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Computers & Operations Research, Volume 32, Issue 3, March 2005, Pages 599–611
2. علامت ها و فرمول ریاضی
2.1. علامت ها
2.2. مدل برنامه نویسی خطی انتگرالی
3. موارد ویژه
3.1. مسئله ی مربوط به (فرمول)
3.2. مسئله ی مربوط به (فرمول)
شکل 1. مثالی که در آن SPT/FAM بهینه نمی باشد.
شکل 2. زمانبندی S ساخته شده از زمانبندی S’
5. الگوریتم چند جمله ای
شکل 3. مثال پروفایل با h = 1.
6. بسط نتیجه
7. نتیجه گیری
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 . 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.