Article: Scheduling a batch processing machine with non-identical job sizes: A clustering perspective

File Download Links for fulltext
(May Require Subscription)
Supplementary
  • Basic View
  • Metadata View
  • XML View
TitleScheduling a batch processing machine with non-identical job sizes: A clustering perspective
AuthorsChen, H2
Du, B2
Huang, GQ1
Keywordsbatch processing machine
clustering
makespan
scheduling
Issue Date2011
PublisherTaylor & Francis Ltd. The Journal's web site is located at http://www.tandf.co.uk/journals/titles/00207543.asp
CitationInternational Journal Of Production Research, 2011, v. 49 n. 19, p. 5755-5778 [How to Cite?]
DOI: http://dx.doi.org/10.1080/00207543.2010.512620
AbstractBatch processing machines that process a group of jobs simultaneously are often encountered in semiconductor manufacturing and metal heat treatment. This paper considered the problem of scheduling a batch processing machine from a clustering perspective. We first demonstrated that minimising makespan on a single batching machine with non-identical job sizes can be regarded as a special clustering problem, providing a novel insight into scheduling with batching. The definition of WRB (waste ratio of batch) was then presented, and the objective function of minimising makespan was transformed into minimising weighted WRB so as to define the distance measure between batches in a more understandable way. The equivalence of the two objective functions was also proved. In addition, a clustering algorithm CACB (constrained agglomerative clustering of batches) was proposed based on the definition of WRB. To test the effectiveness of the proposed algorithm, the results obtained from CACB were compared with those from the previous methods, including BFLPT (best-fit longest processing time) heuristic and GA (genetic algorithm). CACB outperforms BFLPT and GA especially for large-scale problems. © 2011 Taylor & Francis.
ISSN0020-7543
2011 Impact Factor: 1.115
2011 SCImago Journal Rankings: 0.046
DOIhttp://dx.doi.org/10.1080/00207543.2010.512620
ReferencesReferences in Scopus
DC Field
Value
dc.contributor.authorChen, H
dc.contributor.authorDu, B
dc.contributor.authorHuang, GQ
dc.date.accessioned2010-10-31T10:52:21Z
dc.date.available2010-10-31T10:52:21Z
dc.date.issued2011
dc.description.abstractBatch processing machines that process a group of jobs simultaneously are often encountered in semiconductor manufacturing and metal heat treatment. This paper considered the problem of scheduling a batch processing machine from a clustering perspective. We first demonstrated that minimising makespan on a single batching machine with non-identical job sizes can be regarded as a special clustering problem, providing a novel insight into scheduling with batching. The definition of WRB (waste ratio of batch) was then presented, and the objective function of minimising makespan was transformed into minimising weighted WRB so as to define the distance measure between batches in a more understandable way. The equivalence of the two objective functions was also proved. In addition, a clustering algorithm CACB (constrained agglomerative clustering of batches) was proposed based on the definition of WRB. To test the effectiveness of the proposed algorithm, the results obtained from CACB were compared with those from the previous methods, including BFLPT (best-fit longest processing time) heuristic and GA (genetic algorithm). CACB outperforms BFLPT and GA especially for large-scale problems. © 2011 Taylor & Francis.
dc.description.natureLink_to_subscribed_fulltext
dc.identifier.citationInternational Journal Of Production Research, 2011, v. 49 n. 19, p. 5755-5778 [How to Cite?]
DOI: http://dx.doi.org/10.1080/00207543.2010.512620
dc.identifier.doihttp://dx.doi.org/10.1080/00207543.2010.512620
dc.identifier.epage5778
dc.identifier.hkuros178819
dc.identifier.issn0020-7543
2011 Impact Factor: 1.115
2011 SCImago Journal Rankings: 0.046
dc.identifier.issue19
dc.identifier.openurl
dc.identifier.scopuseid_2-s2.0-80051756413
dc.identifier.spage5755
dc.identifier.urihttp://hdl.handle.net/10722/124756
dc.identifier.volume49
dc.languageeng
dc.publisherTaylor & Francis Ltd. The Journal's web site is located at http://www.tandf.co.uk/journals/titles/00207543.asp
dc.publisher.placeUnited Kingdom
dc.relation.ispartofInternational Journal of Production Research
dc.relation.referencesReferences in Scopus
dc.subjectbatch processing machine
dc.subjectclustering
dc.subjectmakespan
dc.subjectscheduling
dc.titleScheduling a batch processing machine with non-identical job sizes: A clustering perspective
dc.typeArticle
Author Affiliations
  1. The University of Hong Kong
  2. University of Science and Technology of China