A genetic algorithm on single machine family scheduling problem to minimise total weighted completion time
In this paper, we address a single machine family scheduling problem where jobs, each characterised by a processing time and an associated positive weight, are partitioned into families and setup time is required between these families. For this problem, we propose a genetic algorithm using an optim...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
EuroJournals
2009
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/12701/ http://psasir.upm.edu.my/id/eprint/12701/1/A%20genetic%20algorithm%20on%20single%20machine%20family%20.pdf |
| _version_ | 1848841906686001152 |
|---|---|
| author | Nazif, Habibeh Lee, Lai Soon |
| author_facet | Nazif, Habibeh Lee, Lai Soon |
| author_sort | Nazif, Habibeh |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | In this paper, we address a single machine family scheduling problem where jobs, each characterised by a processing time and an associated positive weight, are partitioned into families and setup time is required between these families. For this problem, we propose a genetic algorithm using an optimised crossover operator designed by an undirected bipartite graph to find an optimal schedule which minimises the total weighted completion time of the jobs in the presence of the sequence independent family setup times. The proposed algorithm finds the best offspring solution among an exponentially large number of potential offspring. Extensive computational experiments are conducted to assess the efficiency of the proposed algorithm compared to other variants of genetic algorithms. The computational results indicate the effectiveness of the proposed algorithm in generating better quality solutions compared to other algorithms.
|
| first_indexed | 2025-11-15T07:50:41Z |
| format | Article |
| id | upm-12701 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T07:50:41Z |
| publishDate | 2009 |
| publisher | EuroJournals |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-127012015-12-18T03:12:24Z http://psasir.upm.edu.my/id/eprint/12701/ A genetic algorithm on single machine family scheduling problem to minimise total weighted completion time Nazif, Habibeh Lee, Lai Soon In this paper, we address a single machine family scheduling problem where jobs, each characterised by a processing time and an associated positive weight, are partitioned into families and setup time is required between these families. For this problem, we propose a genetic algorithm using an optimised crossover operator designed by an undirected bipartite graph to find an optimal schedule which minimises the total weighted completion time of the jobs in the presence of the sequence independent family setup times. The proposed algorithm finds the best offspring solution among an exponentially large number of potential offspring. Extensive computational experiments are conducted to assess the efficiency of the proposed algorithm compared to other variants of genetic algorithms. The computational results indicate the effectiveness of the proposed algorithm in generating better quality solutions compared to other algorithms. EuroJournals 2009-08 Article PeerReviewed application/pdf en http://psasir.upm.edu.my/id/eprint/12701/1/A%20genetic%20algorithm%20on%20single%20machine%20family%20.pdf Nazif, Habibeh and Lee, Lai Soon (2009) A genetic algorithm on single machine family scheduling problem to minimise total weighted completion time. European Journal of Scientific Research, 35 (3). pp. 444-452. ISSN 1450-216X; ESSN: 1450-202X |
| spellingShingle | Nazif, Habibeh Lee, Lai Soon A genetic algorithm on single machine family scheduling problem to minimise total weighted completion time |
| title | A genetic algorithm on single machine family scheduling problem to minimise total weighted completion time |
| title_full | A genetic algorithm on single machine family scheduling problem to minimise total weighted completion time |
| title_fullStr | A genetic algorithm on single machine family scheduling problem to minimise total weighted completion time |
| title_full_unstemmed | A genetic algorithm on single machine family scheduling problem to minimise total weighted completion time |
| title_short | A genetic algorithm on single machine family scheduling problem to minimise total weighted completion time |
| title_sort | genetic algorithm on single machine family scheduling problem to minimise total weighted completion time |
| url | http://psasir.upm.edu.my/id/eprint/12701/ http://psasir.upm.edu.my/id/eprint/12701/1/A%20genetic%20algorithm%20on%20single%20machine%20family%20.pdf |