Batch Scheduling of Deteriorating Products
Journal Title: Decision Making in Manufacturing and Services - Year 2007, Vol 1, Issue 1
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.
Authors and Affiliations
Maksim S. Barketau, T. C. Edwin Cheng, Mikhail Y. Kovalyov, C. T. Daniel Ng
Keywords
Related Articles
- EP ID EP422425
- DOI 10.7494/dmms.2007.1.2.25
- Views 81
- Downloads 0
A Distributed Decision-Support System for Virtual Prototyping
Virtual Prototyping (VP) is a data-driven design process that promotes both knowledge reuse and innovation. High-profile applications in the automotive and aerospace industries have demonstrated its potential to signific...
Indirect Control of Corporations: Analysis and Simulations
This paper is devoted to indirect control in corporate shareholding networks. This topic is important in financial economics. Since shareholding size does not actually reflect an investor’s power-control in corporate sha...
The Art and Science of Modeling Decision-Making Under Severe Uncertainty
For obvious reasons, models for decision-making under severe uncertainty are austere. Simply put, there is precious little to work with under these conditions. This fact highlights the great importance of utilizing in su...
Editorial
Welcome to the premier issue of the new international journal Decision Making in Manufacturing and Services. The launching of a new journal is a unique opportunity to introduce its mission, scope, and coverage areas.
Optimizing Modular Machining Line Design Problem with Mixed Activation Mode of Machining Units
A modular transfer line designing problem is investigated. The problem is to find the best subset of modules (machining units) from a given set and to assign them to different stations so that technological constraints a...