Simulation-based two-phase genetic algorithm for the capacitated re-entrant line scheduling problem

Jin Young Choi

doi:10.1016/j.cie.2009.01.004

Return

Simulation-based two-phase genetic algorithm for the capacitated re-entrant line scheduling problem

2009-10-01

PRE

Jin Young Choi *

Sung‐Seok Ko

DOI：10.1016/j.cie.2009.01.004

Original

Original request for help

Save

Abstract

En 中文

In this paper, we develop a simulation-based two-phase genetic algorithm for the capacitated re-entrant line scheduling problem. The structure of a chromosome consists of two sub-chromosomes for buffer allocation and server allocation, respectively, while considering all possible states of the system in terms of buffer levels of workstations and assigning a preferred job stage to each component of the chromosome. As an implementation of the suggested algorithm, a job priority-based randomized policy is defined, which reflects the job priority and the properness of local non-idling in allocating buffering and processing capacity to available job instances. The algorithm is combined with a polynomial time sub-optimal deadlock avoidance policy, namely, Bankers algorithm, and the fitness of a chromosome was evaluated based on simulation. The performance of the proposed algorithm is evaluated through a numerical experiment, showing that the suggested approach holds considerable promise for providing effective and computationally efficient approximations to the optimal scheduling policy that consistently outperforms the typically employed heuristics. (C) 2009 Elsevier Ltd. All rights reserved.

Keywords:

Capacitated re-entrant line

Genetic algorithm

Chromosome

Deadlock avoidance

Banker's algorithm

Scheduling

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.