×

Parallel machine scheduling with due date-to-deadline window, order sharing and time value of money. (English) Zbl 1490.90140

Summary: Motivated by a variety of applications in sharing economy, we study an identical parallel machine scheduling problem with due date-to-deadline window by jointly considering machine sharing and the time value of money. A factory owns a set of parallel identical machines and processes a set of production orders within a finite time period. In the sharing setting, the factory may also rent external machines to handle a part of orders by paying some extra cost. The factory aims to determine the sharing policy of the production orders and the scheduling rule of machines, to maximize its total future value of profits by satisfying the orders. To the best of our knowledge, there are no previous results for this problem. In this work, a mathematical programming model is derived, and a problem-specific genetic algorithm and a heuristic are proposed to solve large-scale instances. Numerical experiments using randomly generated instances are carried out to evaluate the effectiveness and efficiency of the proposed solution methods.

MSC:

90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adhau, S, Mittal, ML and Mittal, A (2013). A multi-agent system for decentralized multi-project scheduling with resource transfers. International Journal of Production Economics, 146(2), 646-661.
[2] Alikar, N, Mousavi, SM, Ghazilla, RAR, Tavana, M and Olugu, EU (2017). A bi-objective multi-period series-parallel inventory-redundancy allocation problem with time value of money and inflation considerations. Computers & Industrial Engineering, 104, 51-67.
[3] Chen, W, Wei, L and Li, Y (2018). Fuzzy multicycle manufacturing / remanufacturing production decisions considering inflation and the time value of money. Journal of Cleaner Production, 198, 1494-1502.
[4] Cordone, R, Hosteins, P and Righini, G (2018). A brand-and-bound algorithm for the prize-collecting single-machine scheduling problem with deadlines and total tardiness minimization. INFORMS Journal on Computing, 30(1), 168-180. · Zbl 1446.90076
[5] Chen, R and Yuan, J (2019). Unary NP-hardness of single-machine scheduling to minimize the total tardiness with deadlines. Journal of Scheduling, 22(5), 595-601. · Zbl 1430.90251
[6] Chen, R, Yuan, J, Ng, CT and Cheng, TCE (2019a). Single-machine scheduling with deadlines to minimize the total weighted late work. Naval Research Logistics, 66(7), 582-595. · Zbl 1423.90084
[7] Chen, R, Yuan, J and Lu, L (2019b), Single-machine scheduling with positional due indices and positional deadlines. Discrete Optimization, 34, 1-22. · Zbl 1506.90096
[8] Chandra, MJ and Bahner, ML (1984). The effects of inflation and the time value of money on some inventory systems. International Journal of Production Research, 23(4), 723-730.
[9] Fang, D and Wang, J (2020). Horizontal capacity sharing between asymmetric competitors. Omega-International Journal of Management Science, 97, 102109.
[10] Guo, L and Wu, X (2018). Capacity sharing between competitors, Management Science, 64(8), 3554-3573.
[11] Gong, D, Kang, J, Lin, G and Hou, T (2017). On an IC wire bonding machine production inventory problem with time value of money, International Journal of Production Research, 55(9), 2431-2453.
[12] Hermans, B and Leus, R (2018). Scheduling markovian PERT networks to maximize the net present value: New results, Operations Research Letters, 46(2), 240-244. · Zbl 1525.90204
[13] Johari, M, Hosseini-Motlagh, SM, Nematollahi, M, Goh, M and Ignatius, J (2018). Bi-level credit period coordination for periodic review inventory system with price-credit dependent demand under time value of money, Transportation Research Part E: Logistics and Transportation Review, 114, 270-291.
[14] Kaplan, S and Rabadi, G (2012). Exact and heuristic algorithms for the aerial refueling parallel machine scheduling problem with due date-to-deadline window and ready times, Computers & Industrial Engineering, 62(1), 276-285.
[15] Karla, AR, José, MPO and Mahmoud, MEH (2016). Optimal planning and infrastructure development for shale gas production, Energy Conversion and Management, 119, 91-100.
[16] Li, K, Zhou, T, Liu, B and Li, H (2018). A multi-agent system for sharing distributed manufacturing resources, Expert Systems with Applications, 99, 32-43.
[17] Li, X, Ventura, JA and Bunn, KA (2020). A joint order acceptance and scheduling problem with earliness and tardiness penalties considering overtime, Journal of Scheduling, 125, 200-211. · Zbl 1479.90101
[18] Liu, N, Li, X and Shen, W (2014). Multi-granularity resource virtualization and sharing strategies in cloud manufacturing, Journal of Network and Computer Applications, 46, 72-82.
[19] Liu, Y, Zhang, L, Tao, F and Wang, L (2017). Resource service sharing in cloud manufacturing based on the Gale Shapley algorithm: Advantages and challenge, International Journal of Computer Integrated Manufacturing, 30(4-5), 420-432.
[20] Lawler, EL (1977). A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness, Annals of Discrete Mathematics, 1(8), 331-342. · Zbl 0353.68071
[21] Merkle, D, Middendorf, M and Schmeck, H (2002). Ant colony optimization for resource-constrained project scheduling, IEEE Transactions on Evolutionary Computation, 6(4), 333-346.
[22] Martins, P (2017). Integrating financial planning, loaning strategies and project scheduling on a discrete-time model, Journal of Manufacturing Systems, 44, 217-229.
[23] Nagaraju, D, Rao, AR, Narayanan, S and Pandian, P (2016). Optimal cycle time and inventory decisions in coordinated and non-coordinated two-echelon inventory system under inflation and time value of money, International Journal of Production Research, 54(9), 2709-2730.
[24] Oğuz, C, Salman, FS and Yalçın, ZB (2010). Order acceptance and scheduling decisions in make-to-order systems, International Journal of Production Economics, (9), 1-20.
[25] Qin, J, Wang, K, Wang, Z and Xia, L (2020). Revenue sharing contracts for horizontal capacity sharing under competition, Annals of Operations Research, 291, 731-760. · Zbl 1448.91149
[26] Shirvani, N, Rui, R and Shadrokh, S (2014). Cyclic scheduling of perishable products in parallel machine with release dates, due dates and deadlines, International Journal of Production Economics, 156, 1-12.
[27] Shafahi, A and Haghani, A (2018). Project selection and scheduling for phase-able projects with interdependencies among phases, Automation in Construction, 93, 47-62.
[28] Tadei, R, Grosso, A and Della Croce, F (2002). Finding the Pareto-optima for the total and maximum tardiness single machine problem, Discrete Applied Mathematics, 124(1-3), 117-126. · Zbl 1005.90038
[29] Wu, J, Skouri, K, Teng, J and Hu, Y (2016). Two inventory systems with trapezoidal-type demand rate and time-dependent deterioration and backlogging, Expert Systems with Applications, 46, 367-379.
[30] Xiao, J, Zhang, Z, Bai, L and Liang, H (2016). Determination of the optimal installation site and capacity of battery energy storage system in distribution network integrated with distributed generation, IET Generation Transmission & Distribution, 10(3), 601-607.
[31] Yuan, J (2017). Unary NP-hardness of minimizing the number of tardy jobs with deadlines, Journal of Scheduling, 20(2), 211-218. · Zbl 1373.90065
[32] Yu, C, Jiang, X, Yu, S and Yang, C (2020). Blockchain-based shared manufacturing in support of cyber physical systems: Concept, framework, and operation. Robotics and Computer-Integrated Manufacturing, 64, 101931.
[33] Yan, Z and Liu, L (2018). Advance selling strategies for retailers taking into account the time-value of money, Chinese Journal of Management Review, 30(5), 262-272 (in Chinese)
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.