Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times

Previous Article
Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems
NACO Home
This Issue
Next Article
Optimal dilution strategy for a microbial continuous culture based on the biological robustness

2015, 5(1): 71-77. doi: 10.3934/naco.2015.5.71

Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times

Chengxin Luo ^1,

1.	School of Mathematics and System Science, Shenyang Normal University, 253 Huanghei Northern Street, Shenyang, 110034, China

Received December 2014 Revised March 2015 Published March 2015

Abstract
Related Papers

This paper concerns with a single-machine scheduling problem under batch availability in which both the setup of each batch and the processing times of jobs are controllable by allocating a resource. The completion time of a job in a batch is that of the last job in the batch. Two batch scheduling problems are investigated. The objective is to determine the job sequence, the partition of the job sequence into batches and the resource allocation scheme to minimize makespan, subject to the total amount of resource is bounded by a given value $U$ in the first problem; while in the second problem is to minimize a total cost of makespan and resource without resource limitation, respectively. We show that the problems underlying can be solved in polynomial time and present optimal algorithms.

Keywords: Batch partition, convex optimization., single-machine scheduling, resource assumption, makespan.

Mathematics Subject Classification: Primary: 90B35; Secondary: 47N1.

Citation: Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71

References:

[1]	T. C. E. Cheng, A. Janiak and M. Y. Kovalyov, Single machine batch scheduling with resource dependent setup processing times, European Journal of Operational Research, 135 (2001), 177-183.
[2]	R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 3 (1979), 287-326.
[3]	C. N. Potts, Van Wassenhove and L. Y. Gao, Integrated scheduling with batching and a lot-sizing: a review of algorithms and complexity, Journal of Operational Research Society, 43 (1991), 395-406.
[4]	C. N. Potts and M. Y. Kovalyov, Scheduling with batching: a review, European Journal of Operational Research, 120 (2000), 228-249. doi: 10.1016/S0377-2217(99)00153-8.
[5]	A. Rudek and R. Rudek, A note on optimization in deteriorating systems using scheduling problems with the aging effect and resource allocation models, Computer and Mathematics with Applications, 4 (2011), 1870-1878.
[6]	D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times, Discrete Applied Mathematics, 13 (2007), 1643-1666. doi: 10.1016/j.dam.2007.02.003.
[7]	R. G. Vickson, Two single-machine sequencing problems involing controllable job processing times, AIIE Transactions, 3 (1980), 258-262. doi: 10.1080/05695558008974515.

show all references

References:

[1]	T. C. E. Cheng, A. Janiak and M. Y. Kovalyov, Single machine batch scheduling with resource dependent setup processing times, European Journal of Operational Research, 135 (2001), 177-183.
[2]	R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 3 (1979), 287-326.
[3]	C. N. Potts, Van Wassenhove and L. Y. Gao, Integrated scheduling with batching and a lot-sizing: a review of algorithms and complexity, Journal of Operational Research Society, 43 (1991), 395-406.
[4]	C. N. Potts and M. Y. Kovalyov, Scheduling with batching: a review, European Journal of Operational Research, 120 (2000), 228-249. doi: 10.1016/S0377-2217(99)00153-8.
[5]	A. Rudek and R. Rudek, A note on optimization in deteriorating systems using scheduling problems with the aging effect and resource allocation models, Computer and Mathematics with Applications, 4 (2011), 1870-1878.
[6]	D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times, Discrete Applied Mathematics, 13 (2007), 1643-1666. doi: 10.1016/j.dam.2007.02.003.
[7]	R. G. Vickson, Two single-machine sequencing problems involing controllable job processing times, AIIE Transactions, 3 (1980), 258-262. doi: 10.1080/05695558008974515.

[1]	Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial and Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825
[2]	Hua-Ping Wu, Min Huang, W. H. Ip, Qun-Lin Fan. Algorithms for single-machine scheduling problem with deterioration depending on a novel model. Journal of Industrial and Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040
[3]	Ganggang Li, Xiwen Lu, Peihai Liu. The coordination of single-machine scheduling with availability constraints and delivery. Journal of Industrial and Management Optimization, 2016, 12 (2) : 757-770. doi: 10.3934/jimo.2016.12.757
[4]	Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial and Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058
[5]	Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017
[6]	Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088
[7]	Hongwei Li, Yuvraj Gajpal, C. R. Bector. A survey of due-date related single-machine with two-agent scheduling problem. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1329-1347. doi: 10.3934/jimo.2019005
[8]	Chuanli Zhao, Yunqiang Yin, T. C. E. Cheng, Chin-Chia Wu. Single-machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial and Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691
[9]	Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial and Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323
[10]	Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071
[11]	Shuen Guo, Zhichao Geng, Jinjiang Yuan. Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021192
[12]	Xianzhao Zhang, Dachuan Xu, Donglei Du, Cuixia Miao. Approximate algorithms for unrelated machine scheduling to minimize makespan. Journal of Industrial and Management Optimization, 2016, 12 (2) : 771-779. doi: 10.3934/jimo.2016.12.771
[13]	Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial and Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259
[14]	Ganggang Li, Xiwen Lu. Two-machine scheduling with periodic availability constraints to minimize makespan. Journal of Industrial and Management Optimization, 2015, 11 (2) : 685-700. doi: 10.3934/jimo.2015.11.685
[15]	Mingbao Cheng, Shuxian Xiao, Guosheng Liu. Single-machine rescheduling problems with learning effect under disruptions. Journal of Industrial and Management Optimization, 2018, 14 (3) : 967-980. doi: 10.3934/jimo.2017085
[16]	Muminu O. Adamu, Aderemi O. Adewumi. A survey of single machine scheduling to minimize weighted number of tardy jobs. Journal of Industrial and Management Optimization, 2014, 10 (1) : 219-241. doi: 10.3934/jimo.2014.10.219
[17]	Ata Allah Taleizadeh, Biswajit Sarkar, Mohammad Hasani. Delayed payment policy in multi-product single-machine economic production quantity model with repair failure and partial backordering. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1273-1296. doi: 10.3934/jimo.2019002
[18]	Chaoming Hu, Xiaofei Qian, Shaojun Lu, Xinbao Liu, Panos M Pardalos. Coordinated optimization of production scheduling and maintenance activities with machine reliability deterioration. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021142
[19]	Yuzhong Zhang, Chunsong Bai, Qingguo Bai, Jianteng Xu. Duplicating in batch scheduling. Journal of Industrial and Management Optimization, 2007, 3 (4) : 685-692. doi: 10.3934/jimo.2007.3.685
[20]	Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial and Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Chengxin Luo
on Google Scholar
Chengxin Luo

[Back to Top]