- All Journals
- Al-Qadisiyah University
- Basrah University
- Kirkuk University
- Mosul University
- The Iraqi Borad for Medical Specialization
- University of Anbar
- University of Technology
- Al Mustafa University
- Al-Zahraa University for Women
- Alnoor University
- Kunooz University
- Misan University
- Ninevah University
- Tikrit University
- University of Al-Hamdaniya
- University of Kerbala
Earliness Penalties on A Single Machine Subject To No Tardy Jobs | ||
| Al-Mustansiriyah Journal of Science | ||
| Article 1, Volume 20, Issue 2, 2009, Pages 135-155 | ||
| Author | ||
| Tariq S. Abdul-Razaq | ||
| Abstract | ||
| This study discusses the problem of scheduling n independent jobs on a single machine. The aim of the study is to find the optimal and near optimal schedules that minimizes the total earliness penalties subject to no tardy jobs. The study proposes different lower bounds; the new one which is the best lower bound (LB) for the problem is based on a relaxation on earliness cost to be used in a branch and bound algorithm in order to find an optimal schedule. The derivation of this new LB depends on the earliness cost(which is relaxed) for the sequence obtained by using Smith's backward procedure. We proved some special cases which led to optimal solution, since our problem is NP-hard, some local search methods are also applied such as: Descent method (DM), adjacent pairwise interchange method (APIM), tree type heuristic method (TTHM) and proposed a new method that linking descent method with adjacent pairwise interchange method. We evaluate the performance of these methods on a large set of test problems. 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 optimal solutions for earliness penalties on a single machine subject to no tardy jobs. | ||
|
Statistics Article View: 41 PDF Download: 20 |
||