Skip to main content
SUPERVISOR
Ghasem Moslehi
قاسم مصلحي (استاد راهنما)
 
STUDENT
Niloufar Bolandhemmat
نيلوفر بلندهمت

FACULTY - DEPARTMENT

دانشکده مهندسی صنایع
DEGREE
Master of Science (MSc)
YEAR
1390

TITLE

Single Machine Two-agent Scheduling to Minimize Total Weighted Tardiness with Bounded Maximum Tardiness
In justify; TEXT-INDENT: 14.2pt; MARGIN: 0in 0in 0pt; unicode-bidi: embed; DIRECTION: ltr" But in many situations, different jobs may have different customers, that the difference in their needs applies various objectives to the system. Therefore, in many cases, applying an objective function for all the jobs is not logical and evaluating them is not the same. In multi-agent scheduling, there are a number of different customers, each with several jobs, for the given number of sources. In literature, these customers are called agents. In such problems, there are several agents which have received special attention. Each agent consists of a cost function that only depends on the sequence of its jobs. Thus, having only one general objective function is not considered and each answer should be taken into account according to the function of each agent. In this thesis, two-agent single machine scheduling problem is studied with the objective of minimizing total weighed tardiness for jobs belonging to agent 1, so that the maximum tardiness of second agent is not more than a certain amount. To solve the problem above, two mathematical models and a backward branch and bound procedure with four theorems, lower bound, upper bound, and five dominance rules is presented. Computational results for 2250 generated instances show that the proposed procedure is able to solve 96.66% of instances. Moreover, it is able to solve up to 65 jobs for instances with 2 to 1 ratio of agent 1 and 2, up to 45 instances with equal ratio of agent 1 and 2, and up to 35 instances with 1 to 2 ratio of agent 1 and 2 in 3600 seconds limit of time.
چکيده در مدل هاي متداول زمان بندي، معيار ارزيابي براي همه کارها يا به عبارت ديگر براي تمام مشتريان يکسان است وتوالي کلي از طريق ارزيابي کارها توسط يک معيار مشابه و بدون قائل شدن تفاوت بين آن‌ها سنجيده مي شود. اما در بسياري از مواقع، کارهاي مختلف ممکن است مشتريان متفاوتي داشته باشند که تفاوت در نيازهاي مشتريان، اهداف متفاوتي را به سيستم اعمال مي‌کند. درنتيجه، در بسياري از مواقع ارزيابي کارها مشابه نبوده و اعمال يک تابع هدف براي همه کارها منطقي نيست. در زمان بندي چندعاملي،مشتريان مختلف هر يک با تعدادي کار وجود دارند که براي استفاده از تعدادي منبع محدود رقابت مي کنند. در ادبيات موضوع اين مشتريان عامل ناميده مي‌شوند. در اين گونه مسائل، تعدادي عامل وجود دارند که هر کدام نيازمند توجه ويژه مي‌باشند. هر عاملشامل يک تابع هزينه است که فقط به کارهاي مربوط به خودش در توالي بستگي دارد. در اين گونه مسائل، داشتن تنها يک تابع هدف کلي مد نظر نمي باشد و هر جواب بايد از فرآيندي نتيجه شود که تابع هر عامل را مد نظر قرار مي‌دهد. در اين پايان‌نامه، مسأله زمان‌بندي دو عاملي در محيط تک ماشين با هدف کمينه‌سازي مجموع وزني ديرکرد کارهاي متعلق به عامل اول بررسي مي گردد،به طوري که حداکثر ديرکردکارهايمتعلق به عامل دوم از مقدار معيني بيشتر نباشند. براي حل مسأله فوق دو مدل رياضي ويک رويه شاخه و کران با جستجوي عمقي به صورت پس‌رو معرفي شده و براي روش شاخه و کران4 قضيه، حد پايين و بالا و 5 اصل غلبه ارائهشده است. نتايج محاسباتي براي2250 مسألة نمونة توليد شدهنشان مي‌دهند که رويه شاخه و کران قادر به حل66/96 درصد ازمسائل در محدوديت زماني 3600 ثانيه است و توانايي حل مسائل تا ابعاد 65 کار براي نسبت 2 به 1کارهاي عامل اول و دوم ، ابعاد 45 کار براينسبت برابرکارهاي عامل اول و دوم وابعاد 35 کار براينسبت 1 به 2کارهاي عامل اول و دوم را دارد.

ارتقاء امنیت وب با وف بومی