article

Serial-batching scheduling with time-dependent setup time and effects of deterioration and learning on a single-machine

Authors:

Panos M. Pardalos,

Athanasios Migdalas,

Shanlin YangAuthors Info & Claims

Journal of Global Optimization, Volume 67, Issue 1-2

Pages 251 - 262

https://doi.org/10.1007/s10898-015-0320-5

Published: 01 January 2017 Publication History

Abstract

This paper deals with serial-batching scheduling problems with the effects of deterioration and learning, where time-dependent setup time is also considered. In the proposed scheduling models, all jobs are first partitioned into serial batches, and then all batches are processed on a single serial-batching machine. The actual job processing time is a function of its starting time and position. In addition, a setup time is required when a new batch is processed, and the setup time of the batches is time-dependent, i.e., it is a linear function of its starting time. Structural properties are derived for the problems of minimizing the makespan, the number of tardy jobs, and the maximum earliness. Then, three optimization algorithms are developed to solve them, respectively.

References

[1]

Biskup, D.: Single-machine scheduling with learning considerations. Eur. J. Oper. Res. 115(1), 173---178 (1999)

[2]

Cheng, T.C.E., Wang, G.: Single machine scheduling with learning effect considerations. Ann. Oper. Res. 98(1---4), 273---290 (2000)

[3]

Mosheiov, G., Sidney, J.B.: Scheduling with general job-dependent learning curves. Eur. J. Oper. Res. 147(3), 665---670 (2003)

[4]

Gupta, J.N.D., Gupta, S.K.: Single facility scheduling with nonlinear processing times. Comput. Ind. Eng. 14(4), 387---393 (1988)

Digital Library

[5]

Browne, S., Yechiali, U.: Scheduling deteriorating jobs on a single processor. Oper. Res. 38(3), 495---498 (1990)

Digital Library

[6]

Cheng, T.C.E., Ding, Q., Lin, B.M.T.: A concise survey of scheduling with time-dependent processing times. Eur. J. Oper. Res. 152(1), 1---13 (2004)

[7]

Gawiejnowicz, S.: Time-Dependent Scheduling, Monographs in Theoretical Computer Science, an EATCS Series. Springer, Berlin (2008)

Digital Library

[8]

Jafari, A., Moslehi, G.: Scheduling linear deteriorating jobs to minimize the number of tardy jobs. J. Glob. Optim. 54(2), 389---404 (2012)

Digital Library

[9]

Qi, X.L., Zhou, S.G., Yuan, J.J.: Single machine parallel-batch scheduling with deteriorating jobs. Theor. Comput. Sci. 410(8---10), 830---836 (2009)

Digital Library

[10]

Yang, D.-L., Kuo, W.-H.: A single-machine scheduling problem with learning effects in intermittent batch production. Comput. Ind. Eng. 57(3), 762---765 (2009)

Digital Library

[11]

Li, S.S., Ng, C.T., Cheng, T.C.E., Yuan, J.J.: Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan. Eur. J. Oper. Res. 210(3), 482---488 (2011)

[12]

Miao, C.X., Zhang, Y.Z., Wu, C.L.: Scheduling of deteriorating jobs with release dates to minimize the maximum lateness. Theor. Comput. Sci. 462(30), 80---87 (2012)

Digital Library

[13]

Pei, J., Pardalos, P.M., Liu, X., Fan, W., Yang, S.: Serial batching scheduling of deteriorating jobs in a two-stage supply chain to minimize the makespan. Eur. J. Oper. Res. 244(1), 13---25 (2015)

[14]

Cheng, T.C.E., Lee, W.-C., Wu, C.-C.: Scheduling problems with deteriorating jobs and learning effects including proportional setup times. Comput. Ind. Eng. 58(2), 326---331 (2010)

Digital Library

[15]

Wang, J.-B., Jiang, Y., Wang, G.: Single-machine scheduling with past-sequence-dependent setup times and effects of deterioration and learning. Int. J. Adv. Manuf. Technol. 41(11---12), 1221---1226 (2009)

[16]

Wu, C.-C., Lee, W.-C.: Single-machine group-scheduling problems with deteriorating setup times and job-processing times. Int. J. Prod. Econ. 115(1), 128---133 (2008)

[17]

Pei, J., Liu, X., Fan, W., Pardalos, P.M., Migdalas, A., Yang, S.: Scheduling jobs on a single serial-batching machine with dynamic job arrivals and multiple job types. Ann. Math. Artif. Intell. (2015)

Digital Library

[18]

Pei, J., Liu, X., Pardalos, P.M., Fan, W., Yang, S., Wang, L.: Application of an effective modified gravitational search algorithm for the coordinated scheduling problem in a two-stage supply chain. Int. J. Adv. Manuf. Technol. 70(1---4), 335---348 (2014)

[19]

Yang, S.J.: Group scheduling problems with simultaneous considerations of learning and deterioration effects on a single-machine. Appl. Math. Model. 35(8), 4008---4016 (2011)

[20]

Bai, J., Li, Z.R., Huang, X.: Single-machine group scheduling with general deterioration and learning effects. Appl. Math. Model. 36(3), 1267---1274 (2012)

[21]

Wang, J.B., Gao, W.J., Wang, L.Y., Wang, D.: Single machine group scheduling with general linear deterioration to minimize the makespan. Int. J. Adv. Manuf. Technol. 43, 146---150 (2009)

[22]

Huang, X., Wang, M.Z., Wang, J.B.: Single-machine group scheduling with both learning effects and deteriorating jobs. Comput. Ind. Eng. 60, 750---754 (2011)

Digital Library

[23]

Wang, J.B., Huang, X., Wu, Y.B., Ji, P.: Group scheduling with independent setup times, ready times, and deteriorating job processing times. Int. J. Adv. Manuf. Technol. 60, 643---649 (2012)

[24]

Wang, D., Huo, Y.Z., Ji, P.: Single-machine group scheduling with deteriorating jobs and allotted resource. Optim. Lett. 8, 591---605 (2014)

[25]

Xuan, H., Tang, L.X.: Scheduling a hybrid flowshop with batch production at the last stage. Comput. Oper. Res. 34(9), 2718---2733 (2007)

Digital Library

[26]

Lee, W.C.: A note on deteriorating jobs and learning in single-machine scheduling problems. Int. J. Bus. Econ. 3(1), 83---89 (2004)

[27]

Cheng, T.C.E., Hsu, C.-J., Huang, Y.-C., Lee, W.-C.: Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness. Comput. Oper. Res. 38(12), 1760---1765 (2011)

Digital Library

[28]

Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5, 287---326 (1979)

[29]

Yin, Y., Cheng, S.R., Wu, C.C.: Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties. Inf. Sci. 189, 282---292 (2012)

Digital Library

Cited By

Feng XHu X(2021)A Heuristic Solution Approach to Order Batching and Sequencing for Manual Picking and Packing Lines considering Fatiguing EffectScientific Programming10.1155/2021/88633912021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/8863391
Lu SPei JLiu XQian XMladenovic NPardalos P(2020)Less is more: variable neighborhood search for integrated production and assembly in smart manufacturingJournal of Scheduling10.1007/s10951-019-00619-523:6(649-664)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s10951-019-00619-5
Liao BSong QPei JYang SPardalos P(2020)Parallel-machine group scheduling with inclusive processing set restrictions, outsourcing option and serial-batching under the effect of step-deteriorationJournal of Global Optimization10.1007/s10898-018-0707-178:4(717-742)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s10898-018-0707-1
Show More Cited By

Serial-batching scheduling with time-dependent setup time and effects of deterioration and learning on a single-machine
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

A generalisation model of learning and deteriorating effects on a single-machine scheduling with past-sequence-dependent setup times

This article introduces a general single-machine setup times scheduling model with learning effect and deteriorating jobs simultaneously which is a generalisation of some existing models in the literature. The setup times are proportional to the length ...
Single machine scheduling with time-dependent deterioration and exponential learning effect

In this paper we consider the single machine scheduling problems with time-dependent deterioration and exponential learning effect, i.e., the actual processing time of a job depends not only on the processing times of the jobs already processed but also ...
Single machine scheduling with past-sequence-dependent setup times and learning effects

This paper studies a single machine scheduling problem with setup times and learning considerations. The setup times are proportional to the length of the already scheduled jobs. That is, the setup times are past-sequence-dependent. It is assumed that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Global Optimization

Journal of Global Optimization Volume 67, Issue 1-2

January 2017

440 pages

ISSN:0925-5001

Issue’s Table of Contents

Copyright © Copyright © 2017 Springer Science+Business Media New York.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 January 2017

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Feng XHu X(2021)A Heuristic Solution Approach to Order Batching and Sequencing for Manual Picking and Packing Lines considering Fatiguing EffectScientific Programming10.1155/2021/88633912021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/8863391
Lu SPei JLiu XQian XMladenovic NPardalos P(2020)Less is more: variable neighborhood search for integrated production and assembly in smart manufacturingJournal of Scheduling10.1007/s10951-019-00619-523:6(649-664)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s10951-019-00619-5
Liao BSong QPei JYang SPardalos P(2020)Parallel-machine group scheduling with inclusive processing set restrictions, outsourcing option and serial-batching under the effect of step-deteriorationJournal of Global Optimization10.1007/s10898-018-0707-178:4(717-742)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s10898-018-0707-1
Liao BWang XZhu XYang SPardalos P(2020)Less is more approach for competing groups scheduling with different learning effectsJournal of Combinatorial Optimization10.1007/s10878-019-00452-839:1(33-54)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1007/s10878-019-00452-8
Fan WPei JLiu XPardalos PKong M(2018)Serial-batching group scheduling with release times and the combined effects of deterioration and truncated job-dependent learningJournal of Global Optimization10.1007/s10898-017-0536-771:1(147-163)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s10898-017-0536-7
Sun YQian XLiu S(2018)Scheduling Deteriorating Jobs and Module Changes with Incompatible Job Families on Parallel Machines Using a Hybrid SADE-AFSA AlgorithmLearning and Intelligent Optimization10.1007/978-3-030-05348-2_40(455-472)Online publication date: 10-Jun-2018
https://dl.acm.org/doi/10.1007/978-3-030-05348-2_40
Rudek R(2017)Parallel machine scheduling with general sum of processing time based modelsJournal of Global Optimization10.1007/s10898-017-0509-x68:4(799-814)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s10898-017-0509-x

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents