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.

The article was added to IASJ on 2013-10-03

276 Total full text downloads since the date of addition