American Institute of Mathematical Sciences

Advanced
  • 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

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 & 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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

R. G. Vickson, Two single-machine sequencing problems involing controllable job processing times, AIIE Transactions, 3 (1980), 258-262. doi: 10.1080/05695558008974515.  Google Scholar

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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

R. G. Vickson, Two single-machine sequencing problems involing controllable job processing times, AIIE Transactions, 3 (1980), 258-262. doi: 10.1080/05695558008974515.  Google Scholar

[1]

Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Management Optimization, 2014, 10 (1) : 219-241. doi: 10.3934/jimo.2014.10.219
[17]

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 & Management Optimization, 2021  doi: 10.3934/jimo.2021142
[18]

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 & Management Optimization, 2020, 16 (3) : 1273-1296. doi: 10.3934/jimo.2019002
[19]

Yuzhong Zhang, Chunsong Bai, Qingguo Bai, Jianteng Xu. Duplicating in batch scheduling. Journal of Industrial & 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 & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

 Impact Factor: 

Tools

Metrics

  • PDF downloads (55)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy