File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Metaheuristics to minimise makespan on parallel batch processing machines with dynamic job arrivals

TitleMetaheuristics to minimise makespan on parallel batch processing machines with dynamic job arrivals
Authors
KeywordsAnt Colony Optimisation
Batch Scheduling
Dynamic Job Arrivals
Genetic Algorithm
Makespan
Issue Date2010
PublisherTaylor & Francis Ltd. The Journal's web site is located at http://www.tandf.co.uk/journals/titles/0951192X.asp
Citation
International Journal Of Computer Integrated Manufacturing, 2010, v. 23 n. 10, p. 942-956 How to Cite?
AbstractBatch processing machines that can process a group of jobs simultaneously are often encountered in semiconductor manufacturing and metal heat treatment. This research investigates the scheduling problem on parallel batch processing machines in the presence of dynamic job arrivals and non-identical job sizes. The processing time and ready time of a batch are equal to the largest processing time and release time among all jobs in the batch, respectively. This problem is NP-hard in the strong sense, and hence two lower bounds were proposed to evaluate the performance of approximation algorithms. An ERT-LPT heuristic rule was next presented to assign batches to parallel machines. Two metaheuristics, a genetic algorithm (GA) and an ant colony optimisation (ACO) are further proposed using ERT-LPT to minimise makespan. The performances of the two approaches, along with a BFLPT-ERTLPT (BE) heuristic were compared by computational experiments. The results show that both metaheurisitcs outperform BE. GA is able to obtain better solutions when dealing with small-job instances compared to ACO, whereas ACO dominates GA in large-job instances. © 2010 Taylor & Francis.
Persistent Identifierhttp://hdl.handle.net/10722/155935
ISSN
2023 Impact Factor: 3.7
2023 SCImago Journal Rankings: 0.987
ISI Accession Number ID
Funding AgencyGrant Number
National Natural Science Foundation of China70821001
Research fund for the Doctoral program of Higher Education of China200803580024
HKSAR ITFGHP/042/07LP
HKSAR RGC GRFHKU 712508E
Funding Information:

The authors would like to thank Xiaolin Li, Qi Tan, and Song Zhang for technical assistance. This work was supported by the National Natural Science Foundation of China (70821001), Research fund for the Doctoral program of Higher Education of China (200803580024), HKSAR ITF (GHP/042/07LP) and HKSAR RGC GRF (HKU 712508E).

References
Grants

 

DC FieldValueLanguage
dc.contributor.authorChen, Hen_US
dc.contributor.authorDu, Ben_US
dc.contributor.authorHuang, GQen_US
dc.date.accessioned2012-08-08T08:38:30Z-
dc.date.available2012-08-08T08:38:30Z-
dc.date.issued2010en_US
dc.identifier.citationInternational Journal Of Computer Integrated Manufacturing, 2010, v. 23 n. 10, p. 942-956en_US
dc.identifier.issn0951-192Xen_US
dc.identifier.urihttp://hdl.handle.net/10722/155935-
dc.description.abstractBatch processing machines that can process a group of jobs simultaneously are often encountered in semiconductor manufacturing and metal heat treatment. This research investigates the scheduling problem on parallel batch processing machines in the presence of dynamic job arrivals and non-identical job sizes. The processing time and ready time of a batch are equal to the largest processing time and release time among all jobs in the batch, respectively. This problem is NP-hard in the strong sense, and hence two lower bounds were proposed to evaluate the performance of approximation algorithms. An ERT-LPT heuristic rule was next presented to assign batches to parallel machines. Two metaheuristics, a genetic algorithm (GA) and an ant colony optimisation (ACO) are further proposed using ERT-LPT to minimise makespan. The performances of the two approaches, along with a BFLPT-ERTLPT (BE) heuristic were compared by computational experiments. The results show that both metaheurisitcs outperform BE. GA is able to obtain better solutions when dealing with small-job instances compared to ACO, whereas ACO dominates GA in large-job instances. © 2010 Taylor & Francis.en_US
dc.languageengen_US
dc.publisherTaylor & Francis Ltd. The Journal's web site is located at http://www.tandf.co.uk/journals/titles/0951192X.aspen_US
dc.relation.ispartofInternational Journal of Computer Integrated Manufacturingen_US
dc.subjectAnt Colony Optimisationen_US
dc.subjectBatch Schedulingen_US
dc.subjectDynamic Job Arrivalsen_US
dc.subjectGenetic Algorithmen_US
dc.subjectMakespanen_US
dc.titleMetaheuristics to minimise makespan on parallel batch processing machines with dynamic job arrivalsen_US
dc.typeArticleen_US
dc.identifier.emailHuang, GQ:gqhuang@hkucc.hku.hken_US
dc.identifier.authorityHuang, GQ=rp00118en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1080/0951192X.2010.495137en_US
dc.identifier.scopuseid_2-s2.0-77957121799en_US
dc.identifier.hkuros178824-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77957121799&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume23en_US
dc.identifier.issue10en_US
dc.identifier.spage942en_US
dc.identifier.epage956en_US
dc.identifier.isiWOS:000282129700006-
dc.publisher.placeUnited Kingdomen_US
dc.relation.projectRFID-Enabled Shop-floor Gateway for Real-Time Reconfigurable Manufacturing-
dc.relation.projectRFID-Enabled Real-Time Manufacturing Shop-floor Information Infrastructure for PRD Processing Trade Enterprises-
dc.identifier.scopusauthoridChen, H=35236272300en_US
dc.identifier.scopusauthoridDu, B=36503746800en_US
dc.identifier.scopusauthoridHuang, GQ=7403425048en_US
dc.identifier.issnl0951-192X-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats