research centers


Search results: Found 1

Listing 1 - 1 of 1
Sort by

Article
Earliness Penalties on A Single Machine Subject To No Tardy Jobs

Author: Tariq S. Abdul-Razaq
Journal: Al-Mustansiriyah Journal of Science مجلة علوم المستنصرية ISSN: 1814635X Year: 2009 Volume: 20 Issue: 2 Pages: 135-155
Publisher: Al-Mustansyriah University الجامعة المستنصرية

Loading...
Loading...
Abstract

This study discusses the problem of scheduling n independent jobs on a singlemachine. The aim of the study is to find the optimal and near optimal schedules thatminimizes the total earliness penalties subject to no tardy jobs.The study proposes different lower bounds; the new one which is the bestlower bound (LB) for the problem is based on a relaxation on earliness cost to beused in a branch and bound algorithm in order to find an optimal schedule. Thederivation of this new LB depends on the earliness cost(which is relaxed) for thesequence obtained by using Smith's backward procedure. We proved some specialcases which led to optimal solution, since our problem is NP-hard, some localsearch methods are also applied such as: Descent method (DM), adjacent pairwiseinterchange method (APIM), tree type heuristic method (TTHM) and proposed anew method that linking descent method with adjacent pairwise interchangemethod. We evaluate the performance of these methods on a large set of testproblems. The results, show that (TTH) method is the best, followed by (API) and(DM) methods. Also we present four simple heuristic methods to find near optimalsolutions for earliness penalties on a single machine subject to no tardy jobs.

جدولةالحل الأمثل والحلول التقريبية لتصغير جزاءات التبكير الكلية، بحيث لا يكون ھنالك أعمال متأخرة.( To minimize total earliness penalties subject to no tardy jobs )للمسألة احدھا جديد وھو القيد الأدنى الأحسن (LB) لقد اقترحنا أنواع مختلفة من القيود الدنيالغرض إيجاد الجدولة المثلى . وھذا القيد الأدنى الجديد اشتقاقه (BAB) واستخدم في خوارزمية التفرع والتقيديعتمد على أرخاء دالة الھدف (الكلفة المبكرة) للجدولة والتي نحصل عليھا من استخدام طريقة سمثالتراجعية.لقد برھنا بعض الحالات الخاصة للمسألة والتي تؤدي إلى الحل الأمثل ، بما إن مسألتنا ھي من النوعوطريقة جديدة تربط (DM,APIM,TTHM) قمنا باستخدام طرائق تقريبية مثل ،(NP-hard) الصعبلإيجاد حل قريب من الحل الأمثل . وعند تقيم أداء ھذه الطرق على مجموعة كبيرة من (APIM) مع (DM). (DM) وأخيرا (APIM) أكثر كفاءة ثم (TTHM) المسائل الاختيارية وجدنا إنلقد قدمنا أربع طرق تقريبية لإيجاد حلول قريبة من الحل الأمثل لجزاء التبكير في الماكنة الواحدةللمسالة.

Keywords

Listing 1 - 1 of 1
Sort by
Narrow your search

Resource type

article (1)


Language

English (1)


Year
From To Submit

2009 (1)