Two-agent scheduling with agent specific batches on an unbounded serial batching machine. (English) Zbl 1328.90055
Summary: We study a scheduling problem, in which jobs of two agents are performed in agent specific batches on the same serial unbounded batching machine. On this machine, jobs of the same batch complete simultaneously, and the batch processing time is equal to the total processing time of its jobs plus a setup time. Each agent aims at minimizing a function which depends only on the completion times of its jobs. The problem is to find a schedule that minimizes the objective function of one agent, subject to the objective function of the other agent does not exceed a given threshold. The problem appears in optimizing product consolidation operations of a cross-docking distribution center. Polynomial and pseudo-polynomial dynamic programming algorithms are derived for settings with various combinations of the objective functions.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 90C39 | Dynamic programming |
References:
| [1] | Agnetis, A., Mirchandani, P. B., Pacciarelli, D., & Pacifici, A. (2000). Nondominated schedules for a job-shop with two competing users. Computational & Mathematical Organization Theory, 6, 191-217. · doi:10.1023/A:1009637419820 |
| [2] | Agnetis, A., Mirchandani, P. B., Pacciarelli, D., & Pacifici, A. (2004). Scheduling problems with two competing agents. Operations Research, 52, 229-242. · Zbl 1165.90446 · doi:10.1287/opre.1030.0092 |
| [3] | Agnetis, A., Pacciarelli, D., & Pacifici, A. (2007). Multi-agent single machine scheduling. Annals of Operations Research, 150, 3-15. · Zbl 1144.90375 · doi:10.1007/s10479-006-0164-y |
| [4] | Agnetis, A., Pacciarelli, D. & Pacifici, A. (2008). Combinatorial models for multi agent scheduling problems, In E. Levner (Eds.) Multiprocessor scheduling, theory and applications (pp. 21-46). Vienna, Austria: I-Tech Education and Publishing. ISBN 978-3-902613-02-8. · Zbl 1185.90092 |
| [5] | Albers, S., & Brucker, P. (1993). The complexity of one-machine batching problems. Discrete Applied Mathematics, 47, 87-107. · Zbl 0792.90035 · doi:10.1016/0166-218X(93)90085-3 |
| [6] | Baker, K., & Smith, J. C. (2003). A multiple-criterion model for machine scheduling. Journal of Scheduling, 6, 7-16. · Zbl 1154.90406 · doi:10.1023/A:1022231419049 |
| [7] | Balasubramanian, H., Fowler, J., Keha, A., & Pfund, M. (2009). Scheduling interfering job sets on parallel machines. European Journal of Operational Research, 199, 55-67. · Zbl 1176.90193 · doi:10.1016/j.ejor.2008.10.038 |
| [8] | Brucker, P., & Kovalyov, M. Y. (1996). Single machine batch scheduling to minimize the weighted number of late jobs. Mathematical Methods of Operations Research, 43, 1-8. · Zbl 0842.90058 · doi:10.1007/BF01303431 |
| [9] | Cheng, T. C. E., & Kovalyov, M. Y. (2001). Single machine batch scheduling with sequential job processing. IIE Transactions, 33, 413-420. |
| [10] | Cheng, T. C. E., Kovalyov, M. Y., & Chakhlevich, K. N. (2004). Batching in a two-stage flowshop with dedicated machines in the second stage. IIE Transactions, 36, 87-93. · doi:10.1080/07408170490247368 |
| [11] | 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, 273-281. · Zbl 1100.68007 · doi:10.1016/j.tcs.2006.07.011 |
| [12] | Coffman, E. G, Jr, Yannakakis, M., Magazine, M. J., & Santos, C. A. (1990). Batch sizing and job sequencing on a single machine. Annals of Operations Research, 26, 135-147. · Zbl 0712.90035 · doi:10.1007/BF02248589 |
| [13] | Feng, Q., Yu, Z., & Shang W. (2011). Pareto optimization of serial-batching scheduling problems on two agents. In International conference on advanced mechatronic systems, ICAMechS 2011 (pp. 165-168). Final Program, art. no. 6025008. · Zbl 1233.90163 |
| [14] | Gavranovic, H. & Finke, G. (2000). Graph partitioning and set covering for optimal design of production system in the metal industry. In Proceedings of the second conference on management and control of production and logistics—MCPL’00, Grenobl. · Zbl 1067.90044 |
| [15] | Glass, C. A., Potts, C. N., & Strusevich, V. A. (2001). Scheduling batches with sequential job processing for two-machine flow and open shops. INFORMS Journal on Computing, 13, 120-137. · Zbl 1238.90064 · doi:10.1287/ijoc.13.2.120.10521 |
| [16] | Hall, N. G., & Potts, C. N. (2004). Rescheduling for new orders. Operations Research, 52, 440-453. · Zbl 1165.90456 · doi:10.1287/opre.1030.0101 |
| [17] | Hochbaum, D. S., & Landy, D. (1994). Scheduling with batching: Minimizing the weighted number of tardy jobs. Operations Research Letters, 16, 79-86. · Zbl 0820.90052 · doi:10.1016/0167-6377(94)90063-9 |
| [18] | Hoogeveen, J. (2005). Multicriteria scheduling. European Journal of Operational Research, 167, 592-623. · Zbl 1154.90458 · doi:10.1016/j.ejor.2004.07.011 |
| [19] | Huynh Tuong, N., Soukhal, A., & Billaut, J.-C. (2012). Single-machine multi-agent scheduling problems with a global objective function. Journal of Scheduling, 15(3), 311-321. · Zbl 1280.90074 |
| [20] | Kovalyov, M. Y., Potts, C. N., & Strusevich, V. A. (2004). Batching decisions for assembly production systems. European Journal of Operational Research, 157, 620-642. · Zbl 1067.90044 · doi:10.1016/S0377-2217(03)00250-9 |
| [21] | Kubzin, M. A., & Strusevich, V. A. (2006). Planning machine maintenance in two-machne shop scheduling. Operations Research, 54, 789-800. · Zbl 1167.90669 · doi:10.1287/opre.1060.0301 |
| [22] | Leung, J. Y. T., Pinedo, M., & Wan, G. (2010). Competitive two-agent scheduling and its applications. Operations Research, 58, 458-469. · Zbl 1233.90163 · doi:10.1287/opre.1090.0744 |
| [23] | Li, S., Cheng, T. C. E., Ng, C. T., & Yuan, J. (2014). Two-agent scheduling on a single batching machine. Discrete Applied Mathematics (submitted). · Zbl 0842.90058 |
| [24] | Li, S., & Yuan, J. (2012). Unbounded parallel-batching scheduling with two competitive agents. Journal of Scheduling, 15(5), 629-640. · Zbl 1280.90061 |
| [25] | 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. · Zbl 1238.90069 |
| [26] | Oulamara, A., Finke, G., & Kamgaing Kuiten, A. (2009). Flowshop scheduling problem with batching machine and task compatibilities. Computers & Operations Research, 36, 391-401. · Zbl 1179.90149 · doi:10.1016/j.cor.2007.10.006 |
| [27] | Oulamara, A., Kovalyov, M. Y., & Finke, G. (2005). Scheduling a no-wait flowshop with unbounded batching machines. IIE Transactions on Scheduling and Logistics, 37, 685-696. |
| [28] | Potts, C. N., & Kovalyov, M. Y. (2000). Scheduling with batching: A review. European Journal of Operational Research, 120, 228-249. · Zbl 0953.90028 · doi:10.1016/S0377-2217(99)00153-8 |
| [29] | Potts, C. N., & Van Wassenhove, L. N. (1992). Integrating scheduling with batching and lotsizing: A review of algorithms and complexity. Journal of the Operational Research Society, 42, 395-406. · Zbl 0756.90050 · doi:10.1057/jors.1992.66 |
| [30] | Shen, W., Hao, Q., Joong Yoon, H., & Norrie, D. H. (2006). Applications of agent-based systems in intelligent manufacturing: An updated review. Advanced Engineering Informatics, 20, 415-431. · doi:10.1016/j.aei.2006.05.004 |
| [31] | Tan, Q., Chen, H.-P., Du, B. & Li, X.-L. (2011) Two-agent scheduling on a single batch processing machine with non-identical job sizes. In 2nd international conference on artificial intelligence, management science and electronic commerce, AIMSEC 2011. Proceedings, art. no. 6009883 (pp. 7431-7435). · Zbl 0842.90058 |
| [32] | T’kindt, V., & Billaut, J.-C. (2006). Multicriteria scheduling: Theory, models and algorithms (2nd ed.). Berlin: Springer. · Zbl 1014.90046 |
| [33] | Uzsoy, R., & Yang, Y. (1997). Minimizing total weighted completion time on a single batch processing machine. Production and Operations Management, 6, 57-73. · doi:10.1111/j.1937-5956.1997.tb00415.x |
| [34] | Webster, S., & Baker, K. R. (1995). Scheduling groups of jobs on a single machine. Operations Research, 43, 692-704. · Zbl 0857.90062 · doi:10.1287/opre.43.4.692 |
| [35] | Yazdani Sabouni, M. T., & Jolai, F. (2010). Optimal methods for batch processing problem with makespan and maximum lateness objectives. Applied Mathematical Modelling, 34(2), 314-324. · Zbl 1185.90092 · doi:10.1016/j.apm.2009.04.007 |
| [36] | Yuan, J. J., Shang, W. P., & Feng, Q. (2005). A note on the scheduling with two families of jobs. Journal of Scheduling, 8, 537-542. · Zbl 1123.90040 · doi:10.1007/s10951-005-4997-z |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
