A global constraint for total weighted completion time for unary resources. (English) Zbl 1215.90028
Summary: We introduce a novel global constraint for the total weighted completion time of activities on a single unary capacity resource. For propagating the constraint, we propose an \(O(n ^{4})\) algorithm which makes use of the preemptive mean busy time relaxation of the scheduling problem. The solution to this problem is used to test if an activity can start at each start time in its domain in solutions that respect the upper bound on the cost of the schedule. Empirical results show that the proposed global constraint significantly improves the performance of constraint-based approaches to single-machine scheduling for minimizing the total weighted completion time. We then apply the constraint to the multi-machine job shop scheduling problem with total weighted completion time. Our experiments show an order of magnitude reduction in search effort over the standard weighted-sum constraint and demonstrate that the way in which the job weights are associated with activities is important for performance.
References:
| [1] | Afrati, F., Bampis, E., Chekuri, C., Karger, D., Kenyon, C., Khanna, S., et al. (1999). Approximation schemes for minimizing average weighted completion time with release dates. In Proc. of the 40th IEEE symposium on foundations of computer science (pp. 32–44). |
| [2] | Akkan, C., & Karabatı, S. (2004). The two-machine flowshop total completion time problem: Improved lower bounds and a branch-and-bound algorithm. European Journal of Operational Research, 159, 420–429. · Zbl 1065.90031 · doi:10.1016/S0377-2217(03)00415-6 |
| [3] | Baptiste, Ph., Carlier, J., & Jouglet, A. (2004). A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates. European Journal of Operational Research, 158, 595–608. · Zbl 1056.90054 · doi:10.1016/S0377-2217(03)00378-3 |
| [4] | Baptiste, Ph., & Le Pape, C. (2005). Scheduling a single machine to minimize a regular objective function under setup constraints. Discrete Optimization, 2, 83–99. · Zbl 1140.90390 · doi:10.1016/j.disopt.2004.12.003 |
| [5] | Baptiste, Ph., Peridy, L., & Pinson, E. (2003). A branch and bound to minimize the number of late jobs on a single machine with release time constraints. European Journal of Operational Research, 144(1), 1–11. · Zbl 1037.90022 |
| [6] | Beck, J. C., & Refalo, P. (2003). A hybrid approach to scheduling with earliness and tardiness costs. Annals of Operations Research, 118, 49–71. · Zbl 1026.90039 · doi:10.1023/A:1021849405707 |
| [7] | Belouadah, H., Posner, M. E., & Potts, C. N. (1992). Scheduling with release dates on a single machine to minimize total weighted completion time. Discrete Applied Mathematics, 36, 213–231. · Zbl 0757.90032 · doi:10.1016/0166-218X(92)90255-9 |
| [8] | Belouadah, H., & Potts, C. N. (1994). Scheduling identical parallel machines to minimize total weighted completion time. Discrete Applied Mathematics, 48, 201–218. · Zbl 0809.90073 · doi:10.1016/0166-218X(92)00176-M |
| [9] | Chen, B., Potts, C. N., & Woeginger, G. J. (1998). A review of machine scheduling: Complexity, algorithms and approximation. In Handbook of combinatorial optimization (Vol. 3). Deventer: Kluwer. · Zbl 0944.90022 |
| [10] | Dechter, R., Meiri, I., & Pearl, J. (1991). Temporal constraint networks. Artificial Intelligence, 49, 61–95. · Zbl 0737.68070 · doi:10.1016/0004-3702(91)90006-6 |
| [11] | Della Croce, F., Ghirardi, M., & Tadei, R. (2002). An improved branch-and-bound algorithm for the two machine total completion time flow shop problem. European Journal of Operational Research, 139, 293–301. · Zbl 1001.90065 · doi:10.1016/S0377-2217(01)00374-5 |
| [12] | Demassey, S., Pesant, G., & Rousseau, L.-M. (2006). A cost-regular based hybrid column generation approach. Constraints, 11(4), 315–333. · Zbl 1117.90066 · doi:10.1007/s10601-006-9003-7 |
| [13] | Drexl, A., & Kimms, A. (1997). Lot-sizing and scheduling–survey and extensions. European Journal of Operational Research, 99, 221–235. · Zbl 0923.90067 · doi:10.1016/S0377-2217(97)00030-1 |
| [14] | Dyer, M., & Wolsey, L. A. (1990). Formulating the single machine sequencing problem with release dates as mixed integer program. Discrete Applied Mathematics, 26, 255–270. · Zbl 0694.90060 · doi:10.1016/0166-218X(90)90104-K |
| [15] | Focacci, F., Lodi, A., & Milano, M. (2002). Embedding relaxations in global constraints for solving TSP and TSPTW. Annals of Mathematics and Artificial Intelligence, 34(4), 291–311. · Zbl 1002.68159 · doi:10.1023/A:1014492408220 |
| [16] | Focacci, F., Lodi, A., & Milano, M. (2002). Optimization-oriented global constraints. Constraints, 7(3–4), 351–365. · Zbl 1028.68024 · doi:10.1023/A:1020589922418 |
| [17] | Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York: W.H. Freeman. · Zbl 0411.68039 |
| [18] | Goemans, M. X., Queyranne, M., Schulz, A. S., Skutella, M., & Wang, Y. (2002). Single machine scheduling with release dates. SIAM Journal on Discrete Mathematics, 15(2), 165–192. · Zbl 1009.90096 · doi:10.1137/S089548019936223X |
| [19] | Gomes, C. P., Fernández, C., Selman, B., & Bessière, C. (2005). Statistical regimes across constrainedness regions. Constraints, 10(4), 317–337. · Zbl 1102.68651 · doi:10.1007/s10601-005-2807-z |
| [20] | Jouglet, A., Baptiste, P., & Carlier, J. (2004). Branch-and-bound algorithms for total weighted tardiness. In Handbook of scheduling: Algorithms, models, and performance analysis, chapter 13. London: Chapman & Hall / CRC. · Zbl 1056.90054 |
| [21] | Kovács, A., & Beck, J. C. (2007). Single-machine scheduling with tool changes: A constraint-based approach. In PlanSIG 2007, the 26th workshop of the UK planning and scheduling special interest group (pp. 71–78). |
| [22] | Kovács, A., & Beck, J. C. (2008). A global constraint for total weighted completion time for cumulative resources. Engineering Applications of Artificial Intelligence, 21(5), 691–697. · doi:10.1016/j.engappai.2008.03.004 |
| [23] | Kéri, A., & Kis, T. (2005). Primal-dual combined with constraint propagation for solving rcpspwet. In Proc. of the 2nd multidisciplinary international conference on scheduling: Theory and applications (pp. 748–751). |
| [24] | Le Pape, C., Couronné, P., Vergamini, D., & Gosselin, V. (1994). Time-versus-capacity compromises in project scheduling. In Proceedings of the thirteenth workshop of the UK planning special interest group. |
| [25] | Luby, M., Sinclair, A., & Zuckerman, D. (1993). Optimal speedup of Las Vegas algorithms. Information Processing Letters, 47, 173–180. · Zbl 0797.68139 · doi:10.1016/0020-0190(93)90029-9 |
| [26] | Nessah, R., Yalaoui, F., & Chu, C. (2009). A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates. Computers and Operations Research, 35(4), 1176–1190. · Zbl 1180.90133 · doi:10.1016/j.cor.2006.07.010 |
| [27] | Pan, Y. (2007). Test instances for the dynamic single-machine sequencing problem to minimize total weighted completion time. Available at www.cs.wisc.edu/126yunpeng/test/sm/dwct/instances.htm . |
| [28] | Pan, Y., & Shi, L. (2008). New hybrid optimization algorithms for machine scheduling problems. IEEE Transactions on Automation Science and Engineering, 5(2), 337–348. · doi:10.1109/TASE.2007.895005 |
| [29] | Régin, J.-C. (1999). Arc consistency for global cardinality constraints with costs. In Proceedings of principles and practice of constraint programming (LNCS 1713) (pp. 390–404). |
| [30] | Régin, J.-C. (2003). Global constraints and filtering algorithms. In M. Milano (Ed.), Constraint and integer programming: Toward a unified methodology (pp. 89–135). Deventer: Kluwer. · Zbl 1078.90576 |
| [31] | Régin, J.-C., & Rueher, M. (2005). Inequality-sum: A global constraint capturing the objective function. RAIRO Operations Research, 39, 123–139. · Zbl 1104.90051 · doi:10.1051/ro:2005007 |
| [32] | Scheduler (2002). ILOG Scheduler 6.1 reference manual. ILOG, S.A. |
| [33] | Schulz, A. S. (1996). Scheduling to minimize total weighted completion time: Performance guarantees of lp-based heuristics and lower bounds. In Proc. of the 5th int. conf. on integer programming and combinatorial optimization (pp. 301–315). |
| [34] | Sellmann, M. (2002). An arc consistency algorithm for the minimum weight all different constraint. In Proceedings of principles and practice of constraint programming (LNCS 2470) (pp. 744–749). |
| [35] | van den Akker, J. M., Hurkens, C. A. J, & Savelsberg, M. W. P. (2000). Time-indexed formulations for machine scheduling problems: Column generation. INFORMS Journal on Computing, 12, 111–124. · Zbl 1034.90004 · doi:10.1287/ijoc.12.2.111.11896 |
| [36] | Watson, J. P., Barbulescu, L., Howe, A. E., & Whitley, L. D. (1999). Algorithms performance and problem structure for flow-shop scheduling. In Proceedings of the sixteenth national conference on artificial intelligence (AAAI-99) (pp. 688–695). |
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.
