Minimising makespan for two batch-processing machines with non-identical job sizes in job shop

Bayi Cheng, Shanlin Yang and Ying Ma

International Journal of Systems Science, 2012, vol. 43, issue 12, 2185-2192

Abstract: In this article, the job shop scheduling problem with two batch-processing machines is considered. The machines have limited capacity and the jobs have non-identical job sizes. The jobs are processed in batches and the total size of each batch cannot exceed the machine capacity. The processing times of a job on the two machines are proportional. We show the problem of minimising makespan is NP-hard in the strong sense. Then we provide an approximation algorithm with worst-case ratio no more than 4, and the running time of the algorithm is O(n log n). Finally, the performance of the proposed algorithm is tested by different levels of instances. Computational results demonstrate the effectiveness of the algorithm for all the instances.

Date: 2012
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207721.2011.577250 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tsysxx:v:43:y:2012:i:12:p:2185-2192

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TSYS20

DOI: 10.1080/00207721.2011.577250

Access Statistics for this article

International Journal of Systems Science is currently edited by Visakan Kadirkamanathan

More articles in International Journal of Systems Science from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().