Please use this identifier to cite or link to this item:
Title: Batch scheduling of deteriorating products
Authors: Barketau, MS
Cheng, TCE 
Kovalyov, MY
Ng, CTD 
Keywords: Scheduling
Issue Date: 2007
Publisher: AGH University of Science and Technology Press
Source: Decision making in manufacturing and services, 2007, v. 1, no. 2, p. 25-34 How to cite?
Journal: Decision Making in Manufacturing and Services 
Abstract: In this paper we consider the problem of scheduling N jobs on a single machine, where the jobs are processed in batches and the processing time of each job is a simple linear increasing function depending on job’s waiting time, which is the time between the start of the processing of the batch to which the job belongs and the start of the processing of the job. Each batch starts from the setup time S. Jobs which are assigned to the batch are being prepared for the processing during time S0 < S. After this preparation they are ready to be processed one by one. The non-negative number bi is associated with job i. The processing time of the i-th job is equal to bi(si − (sib + S0)), where sib and si are the starting time of the b-th batch to which the i-th job belongs and the starting time of this job, respectively. The objective is to minimize the completion time of the last job. We show that the problem is NP-hard. After that we present an O(N) time algorithm solving the problem optimally for the case bi = b. We further present an O(N2) time approximation algorithm with a performance guarantee 2.
ISSN: 1896-8325
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

Last Week
Last month
Citations as of Dec 10, 2018

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.