Two-agent scheduling on bounded parallel-batching machines with an aging effect of job-position-dependent | Annals of Operations Research Skip to main content
Springer Nature Link
Log in

Two-agent scheduling on bounded parallel-batching machines with an aging effect of job-position-dependent

  • S.I.: BALCOR-2017
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

This paper investigates a competitive two-agent parallel-batching scheduling problem with aging effect on parallel machines. The objective is to minimize the makespan of agent A with the constraint that the makespan of agent B is no more than a given threshold. Some key structural properties are first identified in two different cases, and based on these structural properties a novel decision tree of scheduling rules is constructed and a heuristic algorithm is designed. Then, an effective hybrid BF-VNS algorithm combining Bacterial Foraging (BF) with variable neighborhood search (VNS) is developed to tackle the studied problem. Computational experiments are conducted to evaluate the performance of the proposed hybrid algorithm and some other well-known algorithms. The experimental results indicate that the hybrid BF-VNS algorithm performs quite better than the compared algorithms.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

References

  • Agnetis, A., Billaut, J. C., Gawiejnowicz, S., Pacciarelli, D., & Soukhal, A. (2014). Multiagent scheduling: Models and algorithms. Berlin: Springer.

    Google Scholar 

  • Agnetis, A., Mirchandani, P. B., Pacciarelli, D., & Pacifici, A. (2004). Scheduling problems with two competing agents. Operations Research, 52(2), 229–242.

    Google Scholar 

  • Arbib, C., Marinelli, F., & Pezzella, F. (2012). An LP-based tabu search for batch scheduling in a cutting process with finite buffers. International Journal of Production Economics, 136(2), 287–296.

    Google Scholar 

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

    Google Scholar 

  • Baker, K. R., & Smith, J. C. (2003). A multiple-criterion model for machine scheduling. Journal of Scheduling, 6, 7–16.

    Google Scholar 

  • Barketau, M. S., Cheng, T. C. E., & Kovalyov, M. Y. (2008). Batch scheduling of deteriorating reworkables. European Journal of Operational Research, 189(3), 1317–1326.

    Google Scholar 

  • Cheng, T. C. E., Chung, Y. H., Liao, S. C., & Lee, W. C. (2013). Two-agent singe-machine scheduling with release times to minimize the total weighted completion time. Computers & Operations Research, 40(1), 353–361.

    Google Scholar 

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

    Google Scholar 

  • Cheng, T. C. E., Ng, C. T., & Yuan, J. J. (2006). Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theoretical Computer Science, 362(1), 273–281.

    Google Scholar 

  • Cheng, T. C. E., Ng, C. T., & Yuan, J. J. (2008). Multi-agent scheduling on a single machine with max-form criteria. European Journal of Operational Research, 188(2), 603–609.

    Google Scholar 

  • Cheng, T. C. E., Wu, W. H., Cheng, S. R., & Wu, C. C. (2011). Two-agent scheduling with position-based deteriorating jobs and learning effects. Applied Mathematics and Computation, 217(21), 8804–8824.

    Google Scholar 

  • Choi, B. C., & Park, M. J. (2015). A batch scheduling problem with two agents. Asia-Pacific Journal of Operational Research, 32(06), 1550044.

    Google Scholar 

  • Devi, S., & Geethanjali, M. (2014). Application of modified bacterial foraging optimization algorithm for optimal placement and sizing of distributed generation. Expert Systems with Applications, 41(6), 2772–2781.

    Google Scholar 

  • Diakité, S., Nicod, J. M., Philippe, L., & Toch, L. (2012). Assessing new approaches to schedule a batch of identical intree-shaped workflows on a heterogeneous platform. Parallel Algorithms and Applications, 27(1), 29.

    Google Scholar 

  • Fan, B. Q., Cheng, T. C. E., Li, S. S., & Feng, Q. (2013). Bounded parallel-batching scheduling with two competing agents. Journal of Scheduling, 16(3), 261–271.

    Google Scholar 

  • Feng, Q., Yuan, J., Liu, H., & He, C. (2013). A note on two-agent scheduling on an unbounded parallel-batching machine with makespan and maximum lateness objectives. Applied Mathematical Modelling, 37(10–11), 7071–7076.

    Google Scholar 

  • Gawiejnowicz, S. (2008). Time-dependent scheduling. Berlin: Springer.

    Google Scholar 

  • Gawiejnowicz, S., Lee, W. C., Lin, C. L., & Wu, C. C. (2011). Single-machine scheduling of proportionally deteriorating jobs by two agents. The Journal of the Operational Research Society, 62(11), 1983–1991.

    Google Scholar 

  • Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5(1), 287–326.

    Google Scholar 

  • Gu, M., Gu, J. W., & Lu, X. W. (2018). An algorithm for multi-agent scheduling to minimize the makespan on m parallel machines. Journal of Schedule, 21(5), 483–492.

    Google Scholar 

  • Gupta, J. N. D., & Gupta, S. K. (1988). Single facility scheduling with nonlinear processing times. Computers & Industrial Engineering, 14(4), 387–393.

    Google Scholar 

  • Hansen, P., Mladenovic, N., Brimberg, J., & Perez, J. A. M. (2003). Variable neighborhood search. In Kochenberger Glover (Ed.), Handbook of metaheuristics (pp. 621–757). London: Kluwer Academic Publishers.

    Google Scholar 

  • Jiang, L., Pei, J., Liu, X., Pardalos, P. M., Yang, Y., & Qian, X. (2017). Uniform parallel batch machines scheduling considering transportation using a hybrid DPSO-GA algorithm. The International Journal of Advanced Manufacturing Technology, 89(5–8), 1887–1990.

    Google Scholar 

  • Kim, D., Abraham, A., & Cho, J. H. (2007). A hybrid genetic algorithm and bacterial foraging approach for global optimization. Information Sciences, 177(18), 3918–3937.

    Google Scholar 

  • Kovalyov, M. Y., Oulamara, A., & Soukhal, A. (2015). Two-agent scheduling with agent specific batches on an unbounded serial batching machine. Journal of Scheduling, 18(4), 423–434.

    Google Scholar 

  • Lee, W. C., Chung, Y. H., & Wang, J. Y. (2016). A parallel-machine scheduling problem with two competing agents. Engineering Optimization, 49(6), 962–975.

    Google Scholar 

  • Lee, W. C., Wang, W. J., Shiau, Y. R., & Wu, C. C. (2010). A single-machine scheduling problem with two-agent and deteriorating jobs. Applied Mathematical Modelling, 34(10), 3098–3107.

    Google Scholar 

  • Lei, D. (2015). Variable neighborhood search for two-agent flow shop scheduling problem. Computers & Operations Research, 80, 125–131.

    Google Scholar 

  • Leung, J. Y. T., Pinedo, M., & Wan, G. (2010). Competitive two-agent scheduling and its applications. Operations Research, 58(2), 458–469.

    Google Scholar 

  • Li, S., Cheng, T. C. E., Ng, C. T., & Yuan, J. (2017). Two-agent scheduling on a single sequential and compatible batching machine. Naval Research Logistics, 64(8), 628–641.

    Google Scholar 

  • Li, S., & Yuan, J. (2012). Unbounded parallel-batching scheduling with two competitive agents. Journal of Scheduling, 15(5), 629–640.

    Google Scholar 

  • Liu, P., Tang, L., & Zhou, X. (2010a). Two-agent group scheduling with deteriorating jobs on a single machine. International Journal of Advanced Manufacturing Technology, 47(5–8), 657–664.

    Google Scholar 

  • Liu, P., Yi, N., & Zhou, X. (2011). Two-agent single-machine scheduling problems under increasing linear deterioration. Applied Mathematical Modelling, 35(5), 2290–2296.

    Google Scholar 

  • Liu, P., Yi, N., Zhou, X., & Gong, H. (2013). Scheduling two agents with sum-of-processing-times-based deterioration on a single machine. Applied Mathematics and Computation, 219(17), 8848–8855.

    Google Scholar 

  • Liu, P., Zhou, X., & Tang, L. (2010b). Two-agent single-machine scheduling with position-dependent processing times. International Journal of Advanced Manufacturing Technology, 48(1–4), 325–331.

    Google Scholar 

  • Liu, X., Lu, S., Pei, J., & Pardalos, P. M. (2017). A hybrid VNS-HS algorithm for a supply chain scheduling problem with deteriorating jobs. International Journal of Production Research. https://doi.org/10.1080/00207543.2017.1418986.

    Article  Google Scholar 

  • Lu, S., Liu, X., Pei, J., Thai, M. T., & Pardalos, P. M. (2018). A hybrid ABC-TS algorithm for the unrelated parallel-batching machines scheduling problem with deteriorating jobs and maintenance activity. Applied Soft Computing, 66, 168–182.

    Google Scholar 

  • Mor, B., & Mosheiov, G. (2011). Single machine batch scheduling with two competing agents to minimize total flowtime. European Journal of Operational Research, 215(3), 524–531.

    Google Scholar 

  • Mosheiov, G. (2001). Scheduling problems with a learning effect. European Journal of Operational Research, 132(3), 687–693.

    Google Scholar 

  • Mosheiov, G., & Oron, D. (2008). A single machine batch scheduling problem with bounded batch size. European Journal of Operational Research, 18(3), 1069–1079.

    Google Scholar 

  • Ozturk, O., Begen, M. A., & Zaric, G. S. (2017). A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan. International Journal of Production Research, 55(6), 1815–1831.

    Google Scholar 

  • Pan, Q.-K., Tasgetiren, M. F., & Liang, Y. C. (2011). A discrete particle optimization algorithm for the no-wait flowshop scheduling problem. Computer & Operations Research, 35(9), 2807–2839.

    Google Scholar 

  • Pandi, V. R., Panigrahi, B. K., Hong, W. C., & Sharma, R. (2014). A multiobjective bacterial foraging algorithm to solve the environmental economic dispatch problem. Energy Sources, Part B: Economics, Planning and Policy, 9(3), 236–247.

    Google Scholar 

  • Pandit, N., Tripathi, A., Tapaswi, S., & Pandit, M. (2012). An improved bacterial foraging algorithm for combined static/dynamic enviromental economic dispatch. Applied Soft Computing, 12(11), 3500–3513.

    Google Scholar 

  • Pang, B., Song, Y., Zhang, C. J., Wang, H. L., & Yang, R. T. (2018). Bacterial foraging optimization based on improved chemotaxis process and novel swarming strategy. Applied Intelligence. https://doi.org/10.1007/s10489-018-1317-9.

    Article  Google Scholar 

  • Passino, K. M. (2002). Biomimicry of bacterial foraging for distributed optimization. IEEE Control Systems, 22(3), 52–67.

    Google Scholar 

  • Pei, J., Darzic, Z., Drazic, M., Mladenovic, N., & Pardalos, P. M. (2018b). Continuous variable neighborhood search (C-VNS) for solving systems of nonlinear equations. INFORMS Journal on Computing. https://doi.org/10.1287/ijoc.2018.0876.

    Article  Google Scholar 

  • Pei, J., Liu, X., Fan, W., Pardalos, P. M., & Lu, S. (2017a). A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs financial budget and resource constraint in multiple manufacturers. Omega. https://doi.org/10.1016/j.omega.2017.12.003.

    Article  Google Scholar 

  • Pei, J., Liu, X., Pardalos, P. M., Fan, W., & Yang, S. (2017b). Scheduling deteriorating jobs on a single serial-batching machine with multiple job types and sequence-dependent setup times. Annals of Operations Research, 249(1–2), 175–195.

    Google Scholar 

  • Pei, J., Liu, X., Pardalos, P. M., Fan, W., Yang, S., & Wang, L. (2014). Application of an effective modified gravitational search algorithm for the coordinated scheduling problem in a two-stage supply chain. International Journal of Advanced Manufacturing Technology, 70(1–4), 335–348.

    Google Scholar 

  • Pei, J., Pardalos, P. M., Liu, X., Fan, W., & Yang, S. (2015). Serial batching scheduling of deteriorating jobs in a two-stage supply chain to minimize the makespan. European Journal of Operational Research, 244(1), 13–25.

    Google Scholar 

  • Pei, J., Wang, X., Fan, W., & Pardalos, P. M. (2018a). Scheduling step-deteriorating jobs on bounded parallel-batching machines to maximise the total net revenue. Journal of the Operational Research Society. https://doi.org/10.1080/01605682.2018.1464428.

    Article  Google Scholar 

  • Tang, L., Zhao, X., Liu, J., & Leung, J. Y. T. (2017). Competitive two-agent scheduling with deteriorating jobs on a single parallel-batching machine. European Journal of Operational Research, 263(2), 401–411.

    Google Scholar 

  • Wan, G., Vakati, S. R., Leung, Y. T., & Pinedo, M. (2010). Scheduling two agents with controllable processing times. European Journal of Operational Research, 205(3), 528–539.

    Google Scholar 

  • Wang, J.-Q., Fan, G. Q., Zhang, Y., Zhang, C. W., & Leung, J. Y. T. (2017). Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes. European Journal of Operational Research, 258(2), 478–490.

    Google Scholar 

  • Wang, J., Zhong, D., Adeli, H., Wang, D., & Liu, M. (2018). Smart bacteria-foraging algorithm-based customized kernel support vector regression and enhanced probabilistic neural network for compaction quality assessment and control of earth-rock dam. Expert Systems. https://doi.org/10.1111/exsy.12357.

    Article  Google Scholar 

  • Wang, Z., Wei, C. M., & Wu, Y. B. (2016). Single machine two-agent scheduling with deteriorating jobs. Asia-Pacific Journal of Operational Research, 33(5), 191–217.

    Google Scholar 

  • Wu, W. H., Cheng, S. R., Wu, C. C., & Yin, Y. (2012). Ant colony algorithms for a two-agent scheduling with sum-of processing times-based learning and deteriorating considerations. Journal of Intelligent Manufacturing, 23(5), 1985–1993.

    Google Scholar 

  • Wu, W. H., Xu, J., Wu, W. H., Yin, Y., Cheng, I. F., & Wu, C. C. (2013). A tabu method for a two-agent single-machine scheduling with deterioration jobs. Computers & Operations Research, 40(8), 2116–2127.

    Google Scholar 

  • Yin, Y., Cheng, T. C. E., Wan, L., Wu, C. C., & Liu, J. (2015). Two-agent single-machine scheduling with deteriorating jobs. Computers & Industrial Engineering, 81, 177–185.

    Google Scholar 

  • Yin, Y., Li, D., Wang, D., & Cheng, T. C. E. (2018). Single-machine serial-batch delivery scheduling with two competing agents and due date assignment. Annals of Operations Research. https://doi.org/10.1007/s10479-018-2839-6.

    Article  Google Scholar 

  • Yin, Y., Wang, Y., Cheng, T. C. E., Wang, D. J., & Wu, C. C. (2016). Two-agent single-machine scheduling to minimize the batch delivery cost. Computers & Industrial Engineering, 92, 16–30.

    Google Scholar 

  • Zhang, B., Pan, Q. K., Gao, L., Zhang, X. L., & Chen, Q. D. (2018a). A hybrid variable neighborhood search algorithm for the hot rolling batch scheduling problem in compact strip production. Computers & Industrial Engineering, 116, 22–36.

    Google Scholar 

  • Zhang, C. L., Wang, J. Q., & Zhang, C. W. (2018b). Two-agent scheduling on a single parallel-batching machine to minimize the weighted sum of the agents’ makespans. Journal of Ambient Intelligence and Humanized Computing. https://doi.org/10.1007/s12652-018-0741-3.

    Article  Google Scholar 

  • Zhou, S. C., Li, X. L., Du, N., Pang, Y., & Chen, H. P. (2018). A multi-objective differential evolution algorithm for parallel batch processing machine scheduling considering electricity consumption cost. Computers & Operations Research, 96, 55–68.

    Google Scholar 

Download references

Acknowledgements

This work is supported by the National Natural Science Foundation of China (Nos. 71871080, 71601065, 71501058, 71690235, 71531008), and Innovative Research Groups of the National Natural Science Foundation of China (71521001), the Humanities and Social Sciences Foundation of the Chinese Ministry of Education (No. 15YJC630097), and Base of Introducing Talents of Discipline to Universities for Optimization and Decision-making in the Manufacturing Process of Complex Product (111 project).

Author information

Authors and Affiliations

  1. School of Management, Hefei University of Technology, Hefei, China

    Jun Pei, Jinling Wei, Baoyu Liao & Xinbao Liu

  2. Key Laboratory of Process Optimization and Intelligent Decision-making of Ministry of Education, Hefei, China

    Jun Pei, Baoyu Liao & Xinbao Liu

  3. Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, Gainesville, USA

    Jun Pei & Panos M. Pardalos

Authors
  1. Jun Pei
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jinling Wei
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Baoyu Liao
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xinbao Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Panos M. Pardalos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Jun Pei or Xinbao Liu.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pei, J., Wei, J., Liao, B. et al. Two-agent scheduling on bounded parallel-batching machines with an aging effect of job-position-dependent. Ann Oper Res 294, 191–223 (2020). https://doi.org/10.1007/s10479-019-03160-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-019-03160-y

Keywords

Search

Navigation