Skip to main content
SpringerLink
Log in

Unrelated parallel-machine scheduling with position-dependent deteriorating jobs and resource-dependent processing time

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

This paper is to analyze unrelated parallel-machine scheduling resource allocation problems with position-dependent deteriorating jobs. Two general resource consumption functions, the linear and convex resource, are investigated. The objectives are to minimize the cost function that includes the weights of total load, total completion time, total absolute deviation of completion time, and total resource cost. Moreover, we try to minimize the cost function that includes the weights of total load, total waiting time, total absolute deviation of waiting time, and total resource cost. Although each job processing time can be compressed through incurring an additional cost, we show that the problems are polynomial time solvable when the number of machines is fixed.

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

Similar content being viewed by others

References

  1. Alidaee, B., Womer, N.K.: Scheduling with time dependent processing times: Review and extensions. J. Oper. Res. Soc. 50, 711–720 (1999)

    MATH  Google Scholar 

  2. Bachman, A., Janiak, A.: Scheduling deteriorating jobs dependent on resources for the makespan minimization. In: Operations Research Proceedings 2000: Selected Papers of the Symposium on Operations Research, Dresden, pp. 29–34, Springer, Berlin (2000)

  3. Bagchi, U.B.: Simultaneous minimization of mean and variation of flow-time and waiting time in single-machine systems. Oper. Res. 37, 118–125 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  4. Browne, S., Yechiali, U.: Dynamic priority rules for cyclic type queues. Adv. Appl. Probab. 10, 432–450 (1989)

    Article  MathSciNet  Google Scholar 

  5. Browne, S., Yechiali, U.: Scheduling deteriorating jobs on a single process. Oper. Res. 38, 495–498 (1990)

    Article  MATH  Google Scholar 

  6. Brucker, P.: Scheduling Algorithms. Springer, Berlin (2001)

    Book  MATH  Google Scholar 

  7. 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–13 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  8. Gawiejnowicz, S.: Time-Dependent Scheduling. Springer, New York (2008)

    MATH  Google Scholar 

  9. Gawiejnowicz, S., Kononov, A.: Complexity and approximability of scheduling resumable proportionally deteriorating jobs. Eur. J. Oper. Res. 200, 305–308 (2010)

    Article  MATH  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  12. Huang, X., Wang, M.-Z.: Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties. Appl. Math. Model. 35, 1349–1353 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  13. Kanet, J.J.: Minimizing variation of flow time in single machine systems. Manag. Sci. 27, 1453–1459 (1981)

    Article  MATH  Google Scholar 

  14. Kunnathur, A.S., Gupta, S.K.: Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem. Eur. J. Oper. Res. 47, 56–62 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  15. Koulamas, C., Gupta, S., Kyparisis, G.J.: A unified analysis for the single-machine scheduling problem with controllable and non-controllable variable job processing times. Eur. J. Oper. Res. 205, 479–482 (2010)

    Article  MATH  Google Scholar 

  16. Lee, W.C., Lai, P.J., Wu, C.C.: Some single-machine and flowshop scheduling problems with a non-linear deterioration function. Comput. Math. Appl. 62, 2487–2496 (2011)

    Google Scholar 

  17. Lu, Y.-Y., Li, G., Wu, Y.-B., Ji, P.: Optimal due-date assignment problem with learning effect and resource-dependent processing times. Optim. Lett. (2012). doi:10.1007/s11590-012-0467-7

  18. Low, C.Y., Hsu, C.-J., Su, C.-T.: Minimizing the makespan with an availability constraint on a single machine under simple linear deterioration. Comput. Math. Appl. 56, 257–265 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  19. Mosheiov, G.: V-shaped policies for scheduling deteriorating jobs. Oper. Res. 39, 979–991 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  20. Ng, C.T., Wang, J.-B., Cheng, T.C.E., Liu, L.L.: A branch-and-bound algorithm for solving a two-machine flow shop problem with deteriorating jobs. Comput. Oper. Res. 37, 83–90 (2010)

    Google Scholar 

  21. Ravetti, M.G., Mateus, G.R., Rocha, P.L., Pardalos, P.M.: Ascheduling problem with unrelated parallel machines and sequence dependent setups. Int. J. Oper. Res. 2, 380–399 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  22. Rocha, P.L., Mateus, G.R., Ravetti, M.G., Pardalos, P.M.: Solving parallel machines scheduling problems with sequence-dependent setup times using variable neighborhood search. IMA J. Manag. Math. 18, 101–115 (2007)

    Google Scholar 

  23. Rocha, P.L., Ravetti, M.G., Mateus, G.R., Pardalos, P.M.: Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times. Comput. Oper. Res. 35, 1250–1264 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  24. Shabtay, D., Steiner, G.: A survey of scheduling with controllable processing times. Discret. Appl. Math. 155, 1643–1666 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  25. Shylo, O., Korenkevych, D., Pardalos, P.M.: Global equilibrium search algorithms for combinatorial optimization problems. Lecture Notes Comput. Sci. 7492, 277–286 (2012)

    Article  Google Scholar 

  26. Vickson, R.G.: Two single machine sequencing problems involving controllable job processing times. AIIE Trans. 12, 258–262 (1980)

    Article  MathSciNet  Google Scholar 

  27. Wang, D., Wang, M.-Z., Wang, J.-B.: Single-machine scheduling with learning effect and resource-dependent processing times. Comput. Ind. Eng. 59, 458–462 (2010)

    Article  Google Scholar 

  28. Wang, J.-B., Wang, J.-J., Ji, P.: Scheduling jobs with chain precedence constraints and deteriorating jobs. J. Oper. Res. Soc. 62, 1765–1770 (2011)

    Article  Google Scholar 

  29. Wang, J.-B., Wang, M.-Z.: Single-machine scheduling with nonlinear deterioration. Optim. Lett. 6, 87–98 (2012)

    Google Scholar 

  30. Wang, J.-B., Wang, M.-Z.: Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time. Comput. Oper. Res. 39, 492–497 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  31. Wang, J.-B., Wang, M.-Z., Ji, P.: Single machine total completion time minimization scheduling with a time-dependent learning effect and deteriorating jobs. Int. J. Syst. Sci. 43, 861–868 (2012)

    Article  MathSciNet  Google Scholar 

  32. Wang, J.-B., Wei, C.-M.: Parallel machine scheduling with a deteriorating maintenance activity and total absolute differences penalties. Appl. Math. Comput. 217, 8093–8099 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  33. Wang, L.-Y., Huang, X., Ji, P., Feng, E.-M.: Unrelated parallel-machine scheduling with deteriorating maintenance activities to minimize the total completion time. Optim. Lett. (2012). doi:10.1007/s11590-012-0472-x

  34. Wassenhove, V.L.N., Baker, K.R.: A bicriterion approach to time/cost trade-offs in sequencing. Eur. J. Oper. Res. 11, 48–52 (1982)

    Google Scholar 

  35. Wei, C.-M., Wang, J.-B.: Single machine quadratic penalty function scheduling with deteriorating jobs and group technology. Appl. Math. Model. 34, 3642–3647 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  36. Wei, C.-M., Wang, J.-B., Ji, P.: Single-machine scheduling with time-and-resource-dependent processing times. Appl. Math. Model. 62, 792–798 (2012)

    Article  MathSciNet  Google Scholar 

  37. Xue, H., Wang, M.-Z.: Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties. Appl. Math. Model. 35, 1349–1353 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  38. Yang, S.-J., Hsu, C.-J., Yang, D.-L.: Single-machine scheduling and slack due-date assignment with aging effect and deteriorating maintenance. Optim. Lett. 6, 1855–1873 (2012). doi:10.1007/s11590-011-0382-3

  39. Yang, S.-H., Wang, J.-B.: Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration. Appl. Math. Comput. 217, 4819–4826 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  40. Yang, Y., Wang, D.-Z., Wang, D.-W., Ip, W.H., Wang, H.-F.: Single machine group scheduling problems with the effects of deterioration and learning. Acta Autom. Sin. 35, 1290–1295 (2009)

    Article  MATH  Google Scholar 

  41. Zhao, C.-L., Tang, H.-Y.: Single machine scheduling problems with deteriorating jobs. Appl. Math. Comput. 161, 865–874 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  42. Zhao, C.-L., Tang, H.-Y.: A note on two-machine no-wait flow shop scheduling with deteriorating jobs and machine availability constraints. Optim. Lett. 5, 183–190 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  43. Zhu, V.C.Y., Sun, L.Y., Sun, L.H., Li, X.H.: Single-machine scheduling time-dependent jobs with resource-dependent ready times. Comput. Ind. Eng. 58, 84–87 (2010)

    Article  Google Scholar 

  44. Zhu, Z.G., Sun, L.Y., Chu, F., Liu, M.: Single-machine group scheduling with resource allocation and learning effect. Comput. Ind. Eng. 60, 148–157 (2011)

    Article  Google Scholar 

Download references

Acknowledgments

We are grateful to two anonymous reviewers for their helpful comments on an earlier version of this article. This research is supported in part by the National Science Council of the Republic of China, under Grant No. NSC 101-2221-E-252-005. Professor Yang is currently a Fulbright visiting scholar to Oregon State University and he is supported in part by the National Science Council of Republic of China, under grant number NSC-101-2918-I-150-002.

Author information

Authors and Affiliations

  1. Department of Industrial Engineering and Management, Nan Kai, University of Technology, Nan-Tou, 542, Taiwan

    Chou-Jung Hsu

  2. Department of Information Management, National Formosa University, Yun-Lin, 632, Taiwan

    Dar-Li Yang

Authors
  1. Chou-Jung Hsu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dar-Li Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Chou-Jung Hsu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hsu, CJ., Yang, DL. Unrelated parallel-machine scheduling with position-dependent deteriorating jobs and resource-dependent processing time. Optim Lett 8, 519–531 (2014). https://doi.org/10.1007/s11590-012-0594-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-012-0594-1

Keywords

Search

Navigation