A Genetic Algorithm to Minimise the Maximum Lateness on a Single Machine Family Scheduling Problem

Lee, Lai Soon and Nazif, Habibeh (2009) A Genetic Algorithm to Minimise the Maximum Lateness on a Single Machine Family Scheduling Problem. In: 23rd European Conference on Operational Research (EURO XXIII), 5 – 8 Julai 2009, Bonn, Germany.

Full text not available from this repository.

Abstract

Machines Scheduling Problems are one of the classical combinatorial optimization problems which exist in many diverse areas such as transportation, manufacturing system, etc. The main focus is on the efficient allocation of one or more resources to activities over time. In this paper, we consider a Single Machine Family Scheduling Problem where jobs are partitioned into families and setup time is required between these families. Setup includes obtaining tool, positioning work in process, cleanup, etc. In most scheduling research work, the setup time has been considered as either negligible and hence ignored, or considered as part of the processing time. While these assumptions simplify the problem, they adversely affect the solution quality for many applications which require explicit treatment of setup. In this study, we propose an Optimised Crossover Genetic Algorithm (OCGA) for the problem. The objective is to find a schedule which minimises the maximum lateness of the jobs in the presence of the sequence independent family setup times.In brief, the proposed OCGA uses binary representation to encode the problem. During crossover, the OCGA selects two parents from the population and replaces them with two children by an optimized crossover mechanism which designed using an undirected bipartite graph. Various techniques are also introduced to further enhance the solution quality. The OCGA is compared with other well known local search method namely dynamic length tabu search, randomised steepest descent method, and other variants of genetic algorithms using extensive data sets collected from the literatures. All algorithms are coded in ANSI-C using Microsoft Visual C++ 6.0 as the compiler, and run on a Pentium 4, 2.0 GHz computer with 2.0 GB RAM. The results of the extensive computational experiments indicate that the proposed OCGA outperformed other local search methods. We have also found that computational difficulty as measured by relative deviation from the lower bound increases with problem size. In the case of large setup time, jobs tend to form a large batch size with more jobs in a batch to reduce the need of setup time between batches from different families. Therefore, more jobs will miss their assigned due dates. However, with a small setup time, more jobs will meet their respective due dates. Hence when setup time is small more batches are formed which means fewer jobs are to be processed per batch.The proposed OCGA effectively solve the problem with better solution quality compared to other local search methods. We will develop the proposed OCGA to solve the problem of minimising the total (weighted) completion time as future work. The development of OCGA for other optimality criterion such as minimising the total (weighted) tardiness/earliness is also worthy of future research.

Item Type:Conference or Workshop Item (Paper)
Keyword:genetic algorithm, machines scheduling, maximum lateness
Subject:Genetics
Subject:Algorithms
Faculty or Institute:Institute for Mathematical Research
ID Code:8838
Deposited By: Erni Suraya Abdul Aziz
Deposited On:21 Dec 2010 03:56
Last Modified:21 Dec 2010 03:59

Repository Staff Only: Edit item detail

Document Download Statistics

This item has been downloaded for since 21 Dec 2010 03:56.

View statistics for "A Genetic Algorithm to Minimise the Maximum Lateness on a Single Machine Family Scheduling Problem"


Universiti Putra Malaysia Institutional Repository

Universiti Putra Malaysia Institutional Repository is an on-line digital archive that serves as a central collection and storage of scientific information and research at the Universiti Putra Malaysia.

Currently, the collections deposited in the IR consists of Master and PhD theses, Master and PhD Project Report, Journal Articles, Journal Bulletins, Conference Papers, UPM News, Newspaper Cuttings, Patents and Inaugural Lectures.

As the policy of the university does not permit users to view thesis in full text, access is only given to the first 24 pages only.