Journal of Korean Society of Industrial and Systems Engineering (산업경영시스템학회지)

Society of Korea Industrial and System Engineering (한국산업경영시스템학회)
권호 표지
DOI QR코드

DOI QR Code

Two-Agent Single-Machine Scheduling with Linear Job-Dependent Position-Based Learning Effects

작업 종속 및 위치기반 선형학습효과를 갖는 2-에이전트 단일기계 스케줄링

  • Received : 2015.08.06
  • Accepted : 2015.09.17
  • Published : 2015.09.30
Download PDF
⟨ Previous Next ⟩

Abstract

Recently, scheduling problems with position-dependent processing times have received considerable attention in the literature, where the processing times of jobs are dependent on the processing sequences. However, they did not consider cases in which each processed job has different learning or aging ratios. This means that the actual processing time for a job can be determined not only by the processing sequence, but also by the learning/aging ratio, which can reflect the degree of processing difficulties in subsequent jobs. Motivated by these remarks, in this paper, we consider a two-agent single-machine scheduling problem with linear job-dependent position-based learning effects, where two agents compete to use a common single machine and each job has a different learning ratio. Specifically, we take into account two different objective functions for two agents: one agent minimizes the total weighted completion time, and the other restricts the makespan to less than an upper bound. After formally defining the problem by developing a mixed integer non-linear programming formulation, we devise a branch-and-bound (B&B) algorithm to give optimal solutions by developing four dominance properties based on a pairwise interchange comparison and four properties regarding the feasibility of a considered sequence. We suggest a lower bound to speed up the search procedure in the B&B algorithm by fathoming any non-prominent nodes. As this problem is at least NP-hard, we suggest efficient genetic algorithms using different methods to generate the initial population and two crossover operations. Computational results show that the proposed algorithms are efficient to obtain near-optimal solutions.

Keywords

References

  1. Agnetis, A., Mirchandani, P.B., Pacciarelli, D., and Pacifici, A., Scheduling problems with two competing agents. Operations Research, 2004, Vol. 52, No. 2, pp. 229-242. https://doi.org/10.1287/opre.1030.0092
  2. Agnetis, A., Pacciarelli, D., and Pacifici A., Multi-agent single machine scheduling. Annals of Operations Research, 2007, Vol. 150, No. 1, pp. 3-15. https://doi.org/10.1007/s10479-006-0164-y
  3. Bachman, A. and Janiak, A., Scheduling jobs with position-dependent processing times. Journal of the Operational Research Society, 2004, Vol. 55, pp. 257-264. https://doi.org/10.1057/palgrave.jors.2601689
  4. Baker, K.R. and Smith, J.C., A multiple-criterion model for machine scheduling. Journal of Scheduling, 2003, Vol. 6, No. 1, pp. 7-16. https://doi.org/10.1023/A:1022231419049
  5. Biskup D., Single-machine scheduling with learning considerations. European Journal of Operational Research, 1999, Vol. 115, No. 1, pp. 173-178. https://doi.org/10.1016/S0377-2217(98)00246-X
  6. Biskup, D., A state-of-the-art review on scheduling with learning considerations. European Journal of Operational Research, 2008, Vol. 188, No. 2, pp. 315-329. https://doi.org/10.1016/j.ejor.2007.05.040
  7. Chang, P.C., Chen, S.H., and Mani, V., A note on due-date assignment and single machine scheduling with a learning and aging effect. International Journal of Production Economics, 2009, Vol. 117, No. 1, pp. 142-149. https://doi.org/10.1016/j.ijpe.2008.10.004
  8. Cheng, T.C.E. and Wang, G., Single machine scheduling with learning effect considerations. Annals of Operations Research, 2000, Vol. 98, No. 1, pp. 273-290. https://doi.org/10.1023/A:1019216726076
  9. Cheng, T.C.E., Ng, C.T., and Yuna, J.J., Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theoretical Computer Science, 2006, Vol. 362, No. 1-3, pp. 273-281. https://doi.org/10.1016/j.tcs.2006.07.011
  10. Cheng, T.C.E., Wu, W.H., Cheng, S.R., and Wu, C.C., Two-agent scheduling with position-based deterioration jobs and learning effects. Applied Mathematics and Computation, 2011, Vol. 217, No. 1, pp. 8804-8824. https://doi.org/10.1016/j.amc.2011.04.005
  11. Ding, G. and Sun, S., Single-machine scheduling problems with two agents competing for makespan. Life System Modeling and Intelligent Computing, 2010, Vol. 6328, pp. 244-255. https://doi.org/10.1007/978-3-642-15621-2_28
  12. Graham, R.L., Lawler, E.L., Lenstra, J.K., and Rinnooy, Kan AHG., Optimization and approximation in deterministic sequencing and scheduling theory : a survey. Annals of Discrete Mathematics, 1979, Vol. 5, pp. 287-326. https://doi.org/10.1016/S0167-5060(08)70356-X
  13. Hardy, G., Littlewood, J., and Polya, G. Inequalities. London : Cambridge University Press, 1967.
  14. Hillier, F.S. and Lieberman, G.J., Introduction to Operations Research, McGraw Hill, 2015.
  15. Knotts, G., Dror, M., and Hartman, B.C., Agent-based project scheduling. IIE Transactions, 2000, Vol. 32, No. 5, pp. 387-401. https://doi.org/10.1080/07408170008963915
  16. Kuo, W.H. and Yang, D.L., Minimizing the makespan in a single-machine scheduling problem with the cyclic process of an aging effect. Journal of the Operational Research Society, 2008, Vol. 59, pp. 416-420. https://doi.org/10.1057/palgrave.jors.2602363
  17. Lee, W.C., Wang, W.J., Shiau, Y.R., and Wu, C.C., A single-machine scheduling problem with two-agent and deteriorating jobs. Applied Mathematical Modelling, 2010, Vol. 34, No. 10, pp. 3098-3107. https://doi.org/10.1016/j.apm.2010.01.015
  18. Leung, J.Y.T., Pinedo, M.L., and Wan, G., Competitive two-agent scheduling and its applications Operations Research, 2010, Vol. 58, No. 2, pp. 458-469. https://doi.org/10.1287/opre.1090.0744
  19. Li, D.C. and Hsu, P.H., Solving a two-agent single-machine scheduling problem considering learning effect. Computers and Operations Research, 2012, Vol. 39, No. 7, pp. 1644-1651. https://doi.org/10.1016/j.cor.2011.09.018
  20. Liu, P., Yi, N., and Zhou, X., Two-agent single-machine scheduling problems under increasing linear deterioration. Applied Mathematical Modelling, 2011, Vol. 35, No. 5, pp. 2290-2296. https://doi.org/10.1016/j.apm.2010.11.026
  21. Liu, P., Zhou, X., and Tang, L., Two-agent single-machine scheduling with position-dependent processing times. International Journal of Advanced Manufacturing Technology, 2010, Vol. 48, No. 1, pp. 325-331. https://doi.org/10.1007/s00170-009-2259-5
  22. Mitchell, M., An introduction to genetic algorithm, MIT Press, 1996.
  23. Mosheiov, G., A note on scheduling deteriorating jobs. Mathematical and Computer Modelling, 2005, Vol. 41, No. 8-9, pp. 883-886. https://doi.org/10.1016/j.mcm.2004.09.004
  24. Mosheiov, G., Parallel machine scheduling with a learning effect. Journal of the Operational Research Society, 2001, Vol. 52, No. 10, pp. 1165-1169. https://doi.org/10.1057/palgrave.jors.2601215
  25. Ng, C.T., Cheng, T.C.E., and Yuan, J.J., A note on the complexity of the problem of two-agent scheduling on a single machine. Journal of Combinatorial Optimization, 2006, Vol. 12, No. 4, pp. 387-394. https://doi.org/10.1007/s10878-006-9001-0
  26. Pessan, C., Bouquard, J.L., and Neron, E., An unrelated parallel machines model for an industrial production resetting problem. European Journal of Industrial Engineering, 2008, Vol. 2, No. 2, pp. 153-171. https://doi.org/10.1504/EJIE.2008.017349
  27. Wang, J. and Wang, M., Worst-case analysis for flow shop scheduling problems with an exponential learning effect. Journal of the Operational Research Society, 2012, Vol. 63, pp. 130-137. https://doi.org/10.1057/jors.2011.40
  28. Wang, J.B. and Xia, Z.Q., Flow-shop scheduling with a learning effect. Journal of the Operational Research Society, 2005, Vol. 56, pp. 1325-1330. https://doi.org/10.1057/palgrave.jors.2601856
  29. Wu, C.C., Huang, S.K., and Lee, W.C., Two-agent scheduling with learning consideration. Computers and Industrial Engineering, 2011b, Vol. 61, No. 4, pp. 1324-1335. https://doi.org/10.1016/j.cie.2011.08.007
  30. Wu, C.C., Yin, Y., and Cheng, S.R., Some single-machine scheduling problems with a truncation learning effect. Computers and Industrial Engineering, 2011a, Vol. 60, No. 4, pp. 790-795. https://doi.org/10.1016/j.cie.2011.01.016
  31. Wu, W.H., Xu, J., Wu, W.H., Yin, Y., Cheng, I.F., and Wu, C.C., A tabu method for a two-agent singlemachine scheduling with deterioration jobs. Computers and Operations Research, 2013, Vol. 40, No. 8, pp. 2116-2127. https://doi.org/10.1016/j.cor.2013.02.025
  32. Yin, Y., Cheng, S.R., Cheng, T.C.E., Wu, W.H., and Wu, C.C., Two-agent single-machine scheduling with release times and deadlines. International Journal of Shipping and Transport Logistics, 2013, Vol. 5, No. 1, pp. 75-94. https://doi.org/10.1504/IJSTL.2013.050590
  33. Yin, Y., Xu, D., Cheng, S.R., and Wu, C.C., A generalization model of learning and deteriorating effects on a single-machine scheduling with past-sequence-dependent setup times. International Journal of Computer Integrated Manufacturing, 2012, Vol. 25, No. 9, pp. 804-813. https://doi.org/10.1080/0951192X.2012.665189

Cited by

  1. 대형 유통매장의 고객을 위한 IoT기반 드라이브 스루 서비스 시스템 설계 vol.18, pp.11, 2015, https://doi.org/10.5762/kais.2017.18.11.151
  2. 다수의 인공위성-지상국 간 통신 스케줄 최적화 모형 vol.41, pp.1, 2015, https://doi.org/10.11627/jkise.2018.41.1.039