Skip to main content
SpringerLink
Log in

Single-machine scheduling problems with past-sequence-dependent delivery times and position-dependent processing times

  • General Paper
  • Published:
Journal of the Operational Research Society

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

This paper considers single-machine scheduling problems with job delivery times where the actual job processing time of a job is defined by a function dependent on its position in a schedule. We assume that the job delivery time is proportional to the job waiting time. We investigate the minimization problems of the sum of earliness, tardiness, and due-window-related cost, the total absolute differences in completion times, and the total absolute differences in waiting times on a single-machine setting. The polynomial time algorithms are proposed to optimally solve the above objective functions. We also investigate some special cases of the problem under study and show that they can be optimally solved by lower order algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1

Similar content being viewed by others

References

  • Bachman A and Janiak A (2004). Scheduling jobs with position-dependent processing times. Journal of the Operational Research Society 55: 257–264.

    Article  Google Scholar 

  • Bagchi UB (1989). Simultaneous minimization of mean and variation of flow-time and waiting time in single machine systems. Operations Research 37: 118–125.

    Article  Google Scholar 

  • Biskup D (1999). Single-machine scheduling with learning considerations. European Journal of Operational Research 115: 173–178.

    Article  Google Scholar 

  • Biskup D (2008). A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research 188: 315–329.

    Article  Google Scholar 

  • Biskup D and Herrmann J (2008). Single-machine scheduling against due dates with past-sequence-dependent setup times. European Journal of Operational Research 191: 587–592.

    Article  Google Scholar 

  • Cheng TCE and Wang G (2000). Single machine scheduling with learning effect considerations. Annals of Operations Research 98: 273–290.

    Article  Google Scholar 

  • Cheng TCE, Lee WC and Wu CC (2010). Scheduling problems with deteriorating jobs and learning effects including proportional setup times. Computers & Industrial Engineering 58: 326–331.

    Article  Google Scholar 

  • Cheng TCE, Lee WC and Wu CC (2011). Single-machine scheduling with deteriorating jobs and past-sequence-dependent setup times. Applied Mathematical Modelling 35: 1861–1867.

    Article  Google Scholar 

  • Cheng TCE, Yang SJ and Yang D-L (2012). Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity. International Journal of Production Economics 135: 154–161.

    Article  Google Scholar 

  • Graham RL, Lawler EL, Lenstra JK and Rinnooy Kan AHG (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics 5: 287–326.

    Article  Google Scholar 

  • Hardy GH, Littlewood JE and Polya G (1967). Inequalities. Cambridge University Press: London.

    Google Scholar 

  • Hsu CJ, Kuo WH and Yang DL (2011). Unrelated parallel machine scheduling with past-sequence-dependent setup time and learning effects. Applied Mathematical Modelling 35: 1492–1496.

    Article  Google Scholar 

  • Janiak A and Rudek R (2006). Scheduling problems with position dependent job processing times. In: Janiak A (ed). Scheduling in Computer and Manufacturing Systems. Poland: Warszawa, WKL, pp 26–38.

    Google Scholar 

  • Janiak A and Rudek R (2009). Experience based approach to scheduling problems with the learning effect. IEEE Transactions on Systems, Man, and Cybernetics—Part A 39: 344–357.

    Article  Google Scholar 

  • Kanet JJ (1981). Minimizing variation of flow time in single machine systems. Management Science 27: 1453–1459.

    Article  Google Scholar 

  • Koulamas C and Kyparisis GJ (2008). Single-machine scheduling problems with past-sequence-dependent setup times. European Journal of Operational Research 187: 1045–1049.

    Article  Google Scholar 

  • Koulamas C and Kyparisis GJ (2010). Single-machine scheduling problems with past-sequence-dependent delivery times. International Journal of Production Economics 126: 264–266.

    Article  Google Scholar 

  • Kuo WH and Yang DL (2007). Single machine scheduling with past-sequence-dependent setup times and learning effects. Information Processing Letters 102: 22–26.

    Article  Google Scholar 

  • Kuo WH, Hsu CJ and Yang DL (2011). Some unrelated parallel machine scheduling problems with past-sequence-dependent setup time and learning effects. Computers & Industrial Engineering 61: 179–183.

    Article  Google Scholar 

  • Liman SD, Panwalkar SS and Thongmee S (1996). Determination of common due window location in a single machine scheduling problem. European Journal of Operational Research 93: 68–74.

    Article  Google Scholar 

  • Liman SD, Panwalkar SS and Thongmee S (1998). Common due window size and location determination in a single machine scheduling problem. Journal of the Operational Research Society 49: 1007–1010.

    Article  Google Scholar 

  • Mosheiov G (2001). Parallel machine scheduling with a learning effect. Journal of the Operational Research Society 52: 1165–1169.

    Article  Google Scholar 

  • Mosheiov G and Sarig A (2008). A due-window assignment problem with position-dependent processing times. Journal of the Operational Research Society 59: 997–1003.

    Article  Google Scholar 

  • Mosheiov G and Sarig A (2009). Scheduling a maintenance activity and due-window assignment on a single machine. Computers & Operations Research 36: 2541–2545.

    Article  Google Scholar 

  • Mosheiov G and Sarig A (2010a). Scheduling with a common due-window: Polynomially solvable cases. Information Science 180: 1492–1505.

    Article  Google Scholar 

  • Mosheiov G and Sarig A (2010b). Scheduling identical jobs and due-window on uniform machines. European Journal of Operational Research 201: 712–719.

    Article  Google Scholar 

  • Papadimitrou CH and Steiglitz K (1982). Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall: Englewood Cliffs, NJ.

    Google Scholar 

  • Wang JB (2008). Single-machine scheduling with past-sequence-dependent setup times and time-dependent learning effect. Computers & Industrial Engineering 55: 584–591.

    Article  Google Scholar 

  • Wang JB and Li JX (2011). Single machine past-sequence-dependent setup times scheduling with general position-dependent and time-dependent learning effects. Applied Mathematical Modelling 35: 1388–1395.

    Article  Google Scholar 

  • Wang J-B and Wang C (2011). Single-machine due-window assignment problem with learning effect and deteriorating jobs. Applied Mathematical Modelling 35: 4017–4022.

    Article  Google Scholar 

  • Wang JB, Wang D, Wang LY, Lin L, Yin N and Wang WW (2009). Single machine scheduling with exponential time-dependent learning effect and past-sequence-dependent setup times. Computers & Mathematics with Applications 57: 9–16.

    Article  Google Scholar 

  • Wang XR, Wang JB, Gao WJ and Huang X (2010). Scheduling with past-sequence-dependent setup times and learning effects on a single machine. International Journal of Advanced Manufacturing Technology 48: 739–746.

    Article  Google Scholar 

  • Yang SJ, Yang DL and Cheng TCE (2010). Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance. Computers & Operations Research 37: 1510–1514.

    Article  Google Scholar 

  • Yeung WK, Oğuz C and Cheng TCE (2001a). Single-machine scheduling with a common due window. Computers & Operations Research 28: 157–175.

    Article  Google Scholar 

  • Yeung WK, Oğuz C and Cheng TCE (2001b). Minimizing weighted number of early and tardy jobs with a common due window involving location penalty. Annals of Operational Research 108: 33–54.

    Article  Google Scholar 

  • Yeung WK, Oğuz C and Cheng TCE (2004). Two-stage flowshop earliness and tardiness machine scheduling involving a common due window. International Journal of Production Economics 90: 421–434.

    Article  Google Scholar 

  • Yeung WK, Oğuz C and Cheng TCE (2009). Two-machine flow shop scheduling with due window to minimize weighted number of early and tardy jobs. Naval Research Logistics 56: 593–599.

    Article  Google Scholar 

  • Yeung WK, Choi TM and Cheng TCE (2010). Optimal scheduling of a single-supplier single-manufacturer supply chain with common due windows. IEEE Transactions on Automatic Control 55: 2767–2777.

    Article  Google Scholar 

  • Zhao C and Tang H (2012). A note to due-window assignment and single machine scheduling with deteriorating jobs and a rate-modifying activity. Computers & Operations Research 39: 1300–1303.

    Article  Google Scholar 

Download references

Acknowledgements

We thank the Editor and three anonymous reviewers for their helpful comments and suggestions on an earlier version of the paper. This research was supported in part by the National Science Council of Taiwan, Republic of China, under grant numbers NSC 99-2221-E-150-034-MY2 and NSC 100-2221-E-252-002-MY2.

Author information

Authors and Affiliations

  1. Nan Kai University of Technology, Tsao Tun, Taiwan

    S-J Yang

  2. National Formosa University, Yun Lin, Taiwan

    D-L Yang

Authors
  1. S-J Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. D-L Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to D-L Yang.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Yang, SJ., Yang, DL. Single-machine scheduling problems with past-sequence-dependent delivery times and position-dependent processing times. J Oper Res Soc 63, 1508–1515 (2012). https://doi.org/10.1057/jors.2011.155

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2011.155

Keywords

Search

Navigation