Local search algorithms for multi-criteria single machine scheduling problem

Joint Authors

Akram, Abir O.
Abd al-Razzaq, Tariq Salih

Source

مجلة ابن الهيثم للعلوم الصرفة و التطبيقية

Publisher

University of Baghdad College of Education for Pure Science / Ibn al-Haitham

Publication Date

2017-12-31

Country of Publication

Iraq

No. of Pages

16

Main Subjects

Mathematics

English Abstract

Real life scheduling problems require the decision maker to consider a number of criteria before arriving at any decision.

In this paper, we consider the multi-criteria scheduling problem of n jobs on single machine to minimize a function of five criteria denoted by total completion times (∑), total tardiness (∑), total earliness (∑), maximum tardiness () and maximum earliness ().

The single machine total tardiness problem and total earliness problem are already NP-hard, so the considered problem is strongly NP-hard.

We apply two local search algorithms (LSAs) descent method (DM) and simulated annealing method (SM) for the 1// (∑∑∑) problem (SP) to find near optimal solutions.

The local search methods are used to speed up the process of finding a good enough solution, where an exhaustive search is impractical for the exact solution.

The two heuristic (DM and SM) were compared with the branch and bound (BAB) algorithm in order to evaluate effectiveness of the solution methods.

Some experimental results are presented to show the applicability of the (BAB) algorithm and (LSAs).

With a reasonable time, (LSAs) may solve the problem (SP) up to 5000 jobs.

Data Type

Conference Papers

Record ID

BIM-851620

• APA
• MLA
• AMA