More Web Proxy on the site http://driver.im/

article

Single machine group scheduling under decreasing linear deterioration

Authors:

Li-Yan WangAuthors Info & Claims

Journal of Applied Mathematics and Computing, Volume 24, Issue 1

Pages 283 - 293

https://doi.org/10.1007/BF02832317

Published: 01 May 2007 Publication History

Abstract

This paper considers single machine scheduling problems with group technology (GT) and deteriorating jobs. A sequence independent setup is required to process a job from a different group and jobs in each group are processed together. We consider the case of jobs whose processing times are a decreasing function of their starting time. The objectives of scheduling problems are to minimize the makespan and the total completion time, respectively. We also provide polynomial time algorithms to solve these problems.

References

[1]

1. B. Alidaee and N. K. Womer, Scheduling with time dependent processing processing times: review and extensions, Journal of the Operational Research Society 50 (1999), 711-720.

[2]

2. A. Bachman, T. C. E. Cheng, A. Janiak and C. T. Ng, Scheduling start time dependent jobs to minimize the total weighted completion time, Journal of the Operational Research Society 53 (2002), 688-693.

[3]

3. S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor, Operations Research 38 (1990), 495-498.

Digital Library

[4]

4. Z.-L. Chen, Parallel machine scheduling with time dependent processing times Discrete Applied Mathematics 70 (1996), 81-94.

Digital Library

[5]

5. T. C. E. Cheng, Q. Ding and B. M. T. Lin, A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research 152 (2004), 1-13.

[6]

6. 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 5 (1979), 287-326.

[7]

7. K. I.-J. Ho, J. Y.-T. Leung and W.-D. Wei, Complexity of scheduling tasks with time-dependent execution times, Information Processing Letters 48 (1993), 315-320.

Digital Library

[8]

8. Y. C. Hsieh and D. L. Bricker, Scheduling linearly deteriorating jobs on multiple machines, Computers and Industrial Engineering 32 (1997), 727-734.

Digital Library

[9]

9. A. Kononov and S. Gawiejnowicz, NP-hard cases in scheduling deteriorating jobs on dedicated machines, Journal of the Operational Research Society 52 (2001), 708-717.

[10]

10. G. Mosheiov, V-shaped policies for scheduling deteriorating jobs, Operations Research 39 (1991), 979-991.

Digital Library

[11]

11. G. Mosheiov, Scheduling jobs under simple linear deterioration, Computers and Operations Research 21 (1994), 653-659.

Digital Library

[12]

12. G. Mosheiov, Multi-machine scheduling with linear deterioration, INFOR 36 (1998), 205-214.

[13]

13. G. Mosheiov, Complexity analysis of job-shop scheduling with deteriorating jobs, Discrete Applied Mathematics 117 (2002), 195-209.

[14]

14. C. T. Ng, T. C. E. Cheng, A. Bachman and A. Janiak, Three scheduling problems with deteriorating jobs to minimize the total completion time, Information Processing Letters 81 (2002), 327-333.

Digital Library

[15]

15. C. N. Potts and L. N. Van Wassenhove, Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity, Journal of the Operational Research Society 43 (1992), 395-406.

[16]

16. P. S. Sundararaghavan and A. S. Kunnathur, Single machine scheduling with start time dependent processing times: some solvable cases, European Journal of Operational Research 78 (1994), 394-403.

[17]

17. J.-B. Wang and Z.-Q. Xia, Scheduling jobs under decreasing linear deterioration, Information Processing Letters 94 (2005), 63-69.

Digital Library

[18]

18. J.-B. Wang and Z.-Q. Xia, Flow shop scheduling problems with deteriorating jobs under dominating machines, Journal of the Operational Research Society 57 (2006), 220-226.

[19]

19. J.-B. Wang, Flow shop scheduling problems with decreasing linear deterioration under dominant machines, Computers and Operations Research 34(2007), 2043-2058.

Digital Library

Cited By

Cheng THsu CHuang YLee W(2011)Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardinessComputers and Operations Research10.1016/j.cor.2010.11.01438:12(1760-1765)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1016/j.cor.2010.11.014
Wu CShiau YLee W(2008)Single-machine group scheduling problems with deterioration considerationComputers and Operations Research10.1016/j.cor.2006.09.00835:5(1652-1659)Online publication date: 1-May-2008
https://dl.acm.org/doi/10.1016/j.cor.2006.09.008

Index Terms

Single machine group scheduling under decreasing linear deterioration
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

Single-machine group scheduling problems with deterioration consideration

In many realistic situations, a job processed later consumes more time than the same job when it is processed earlier; this phenomenon is known as deteriorating jobs. However, job deterioration is relatively unexplored in the context of group ...
Scheduling jobs under decreasing linear deterioration

This paper considers the scheduling problems under decreasing linear deterioration. Deterioration of a job means that its processing time is a function of its execution start time. Optimal algorithms are presented respectively for single machine ...
Single-machine group scheduling with new models of position-dependent processing times
Highlights
- New scheduling models of position-dependent processing times are proposed.
- The ...
Abstract
We propose new models of position-dependent processing times for single-machine group scheduling problems. The two objectives of the scheduling problems are to minimize the makespan and the total completion time, respectively. We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Applied Mathematics and Computing

Journal of Applied Mathematics and Computing Volume 24, Issue 1

May 2007

443 pages

ISSN:1598-5865

Issue’s Table of Contents

Publisher

The Editorial Office, KJCAM

Chungnam, Korea, Republic of

Publication History

Published: 01 May 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 07 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cheng THsu CHuang YLee W(2011)Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardinessComputers and Operations Research10.1016/j.cor.2010.11.01438:12(1760-1765)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1016/j.cor.2010.11.014
Wu CShiau YLee W(2008)Single-machine group scheduling problems with deterioration considerationComputers and Operations Research10.1016/j.cor.2006.09.00835:5(1652-1659)Online publication date: 1-May-2008
https://dl.acm.org/doi/10.1016/j.cor.2006.09.008

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents