• 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

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.
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,, \emph{European Journal of Operational Research}, 135 (2001), 177.   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,, \emph{Annals of Discrete Mathematics}, 3 (1979), 287.   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,, \emph{Journal of Operational Research Society}, 43 (1991), 395.   Google Scholar

[4]

C. N. Potts and M. Y. Kovalyov, Scheduling with batching: a review,, \emph{European Journal of Operational Research}, 120 (2000), 228.  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,, \emph{Computer and Mathematics with Applications}, 4 (2011), 1870.   Google Scholar

[6]

D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times,, \emph{Discrete Applied Mathematics}, 13 (2007), 1643.  doi: 10.1016/j.dam.2007.02.003.  Google Scholar

[7]

R. G. Vickson, Two single-machine sequencing problems involing controllable job processing times,, \emph{AIIE Transactions}, 3 (1980), 258.  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,, \emph{European Journal of Operational Research}, 135 (2001), 177.   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,, \emph{Annals of Discrete Mathematics}, 3 (1979), 287.   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,, \emph{Journal of Operational Research Society}, 43 (1991), 395.   Google Scholar

[4]

C. N. Potts and M. Y. Kovalyov, Scheduling with batching: a review,, \emph{European Journal of Operational Research}, 120 (2000), 228.  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,, \emph{Computer and Mathematics with Applications}, 4 (2011), 1870.   Google Scholar

[6]

D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times,, \emph{Discrete Applied Mathematics}, 13 (2007), 1643.  doi: 10.1016/j.dam.2007.02.003.  Google Scholar

[7]

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

[1]

Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020174

[2]

Yunfeng Geng, Xiaoying Wang, Frithjof Lutscher. Coexistence of competing consumers on a single resource in a hybrid model. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 269-297. doi: 10.3934/dcdsb.2020140

[3]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122

[4]

Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100

[5]

Hedy Attouch, Aïcha Balhag, Zaki Chbani, Hassan Riahi. Fast convex optimization via inertial dynamics combining viscous and Hessian-driven damping with time rescaling. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021010

[6]

Onur Şimşek, O. Erhun Kundakcioglu. Cost of fairness in agent scheduling for contact centers. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021001

[7]

Yuanshi Wang. Asymmetric diffusion in a two-patch mutualism system characterizing exchange of resource for resource. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 963-985. doi: 10.3934/dcdsb.2020149

[8]

Ying Lin, Qi Ye. Support vector machine classifiers by non-Euclidean margins. Mathematical Foundations of Computing, 2020, 3 (4) : 279-300. doi: 10.3934/mfc.2020018

[9]

Sergio Conti, Georg Dolzmann. Optimal laminates in single-slip elastoplasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 1-16. doi: 10.3934/dcdss.2020302

[10]

Kengo Nakai, Yoshitaka Saiki. Machine-learning construction of a model for a macroscopic fluid variable using the delay-coordinate of a scalar observable. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1079-1092. doi: 10.3934/dcdss.2020352

[11]

Shiqi Ma. On recent progress of single-realization recoveries of random Schrödinger systems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020121

[12]

Attila Dénes, Gergely Röst. Single species population dynamics in seasonal environment with short reproduction period. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020288

[13]

Shahede Omidi, Jafar Fathali. Inverse single facility location problem on a tree with balancing on the distance of server to clients. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021017

[14]

Reza Lotfi, Zahra Yadegari, Seyed Hossein Hosseini, Amir Hossein Khameneh, Erfan Babaee Tirkolaee, Gerhard-Wilhelm Weber. A robust time-cost-quality-energy-environment trade-off with resource-constrained in project management: A case study for a bridge construction project. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020158

[15]

Martin Heida, Stefan Neukamm, Mario Varga. Stochastic homogenization of $ \Lambda $-convex gradient flows. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 427-453. doi: 10.3934/dcdss.2020328

[16]

Tomasz Szostok. Inequalities of Hermite-Hadamard type for higher order convex functions, revisited. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020296

[17]

Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050

[18]

Jiangtao Yang. Permanence, extinction and periodic solution of a stochastic single-species model with Lévy noises. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020371

[19]

Sishu Shankar Muni, Robert I. McLachlan, David J. W. Simpson. Homoclinic tangencies with infinitely many asymptotically stable single-round periodic solutions. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021010

[20]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]