Issue |
RAIRO-Oper. Res.
Volume 52, Number 2, April–June 2018
|
|
---|---|---|
Page(s) | 315 - 334 | |
DOI | https://doi.org/10.1051/ro/2017040 | |
Published online | 31 May 2018 |
Single-machine batch scheduling problem with job rejection and resource dependent processing times
1
School of Mathematics and Computer Science, Yichun University,
Yichun,
Jiangxi,
336000 P.R. China
2
Department of Statistics, Feng Chia University,
Taichung, Taiwan
3
Department of Business Administration, Fu Jen Catholic Universit,
Hsinpei City, Taiwan
* Corresponding author: docchia@gmail.com
Received:
18
October
2016
Accepted:
17
May
2017
This paper addresses single-machine batch scheduling with job rejection and convex resource allocation. A job is either rejected, in which case a rejection penalty will be incurred, or accepted and processed on the machine. The accepted jobs are combined to form batches containing contiguously scheduled jobs. For each batch, a batch-dependent machine setup time, which is a function of the number of batches processed previously, is required before the first job in the batch is processed. Both the setup times and job processing times are controllable by allocating a continuously divisible nonrenewable resource to the jobs. The objective is to determine an accepted job sequence, a rejected job set, a partition of the accepted job sequence into batches, and resource allocation that jointly minimize a cost function based on the total delivery dates of the accepted jobs, and the job holding, resource consumption, and rejection penalties. An dynamic programming solution algorithm with running time O (n6) is developed for the problem. It is also shown that the case of the problem with a common setup time can be solved in O (n5) time.
Mathematics Subject Classification: 90B35 / 90C26
Key words: Scheduling / batching / resource allocation / rejected penalty
© EDP Sciences, ROADEF, SMAI 2018
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.