A branch, bound, and remember algorithm for the \(1|r _{i }|\sum t _{i }\) scheduling problem. (English) Zbl 1179.90139
Summary: This paper presents a modified Branch and Bound (B&B) algorithm called, the Branch, Bound, and Remember (BB&R) algorithm, which uses the Distributed Best First Search (DBFS) exploration strategy for solving the \(1|r _{i }|\sum t _{i }\) scheduling problem, a single machine scheduling problem where the objective is to find a schedule with the minimum total tardiness. Memory-based dominance strategies are incorporated into the BB&R algorithm. In addition, a modified memory-based dynamic programming algorithm is also introduced to efficiently compute lower bounds for the \(1|r _{i }|\sum t _{i }\) scheduling problem. Computational results are reported, which shows that the BB&R algorithm with the DBFS exploration strategy outperforms the best known algorithms reported in the literature.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C39 | Dynamic programming |
References:
| [1] | Baptiste, P., 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 |
| [2] | Baptiste, P., 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 Jornal of Operational Research, 144, 1–11. · Zbl 1037.90022 |
| [3] | Bedworth, D., & Bailey, J. (1987). Integrated production control systems: management, analysis, design. New York: Wiley. |
| [4] | Brucker, P. (1999). Scheduling algorithms, 2nd edn. Heidelberg: Springer. · Zbl 0941.90033 |
| [5] | Chang, S., Lu, Q., Tang, G., & Yu, W. (1995). On decomposition of the total tardiness problem. Operations Research, 17, 221–229. · Zbl 0858.90072 |
| [6] | Chu, C. (1992). A branch-and-bound algorithm to minimize total tardiness with different release dates. Naval Research Logistics, 39, 265–283. · Zbl 0762.90035 · doi:10.1002/1520-6750(199203)39:2<265::AID-NAV3220390209>3.0.CO;2-L |
| [7] | Chu, C., & Portmann, M. C. (1992). Some new efficient methods to solve the n|1|r i | i scheduling problem. European Journal of Operational Research, 58, 404–413. · Zbl 0760.90055 · doi:10.1016/0377-2217(92)90071-G |
| [8] | Dauzère-Pérès, S., & Sevaux, M. (2004). An exact method to minimize the number of tardy jobs in single machine scheduling. Journal of Scheduling, 7, 405–420. · Zbl 1154.90437 · doi:10.1023/B:JOSH.0000046073.05827.15 |
| [9] | Du, J., & Leung, J.Y.-T. (1990). Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, 15, 483–495. · Zbl 0714.90052 · doi:10.1287/moor.15.3.483 |
| [10] | Emmons, H. (1969). One-machine sequencing to minimize certain function of job tardiness. Operations Research, 17, 701–715. · Zbl 0176.50005 · doi:10.1287/opre.17.4.701 |
| [11] | Garfinkel, R., & Nemhauser, G. (1972). Integer programming. New York: Wiley. · Zbl 0259.90022 |
| [12] | Graham, R., Lawler, E., Lenstra, J., & Rinnooy Kan, A. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287–326. · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |
| [13] | Jouglet, A., Baptiste, P., & Carlier, J. (2004). Branch-and-bound algorithms for total weighted tardiness. In J.Y.–T. Leung (Ed.), Handbook of scheduling: algorithms, models, and performance analysis. Boca Raton: CRC Press. · Zbl 1056.90054 |
| [14] | Kao, G. K., Sewell, E. C., Jacobson, S. H., & Hall, S. N. 2008. The distributed best first search exploration strategy: an illustrative example with the 1|r i | i scheduling problem (Technical Report). Department of Computer Science, University of Illinois at Urbana Champaign. |
| [15] | Lawler, E. L. (1977). A pseudo-polynomial algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1, 331–342. · Zbl 0353.68071 · doi:10.1016/S0167-5060(08)70742-8 |
| [16] | Potts, C. N., & Van Wassenhove, L. N. (1982). A decomposition algorithm for the single machine total tardiness problem. Operations Research Letters, 26, 177–182. · Zbl 0508.90045 · doi:10.1016/0167-6377(82)90035-9 |
| [17] | Rinnooy Kan, A. (1976). Machine scheduling problem: classification, complexity and computations. Hague: Nijhoff. |
| [18] | Russell, S., & Norvig, P. (1995). Artificial intelligence: a modern approach. Englewood Cliffs: Prentice Hall. · Zbl 0835.68093 |
| [19] | Sellers, D. W. 1996. A survey of approaches to the job shop scheduling problem. In 28th Southeastern symposium on system theory (p. 396). |
| [20] | Szwarc, W., Della Croce, F., & Grosso, A. (1999). Solution of the single-machine total tardiness problem. Journal of Scheduling, 2, 55–71. · Zbl 0963.90029 · doi:10.1002/(SICI)1099-1425(199903/04)2:2<55::AID-JOS14>3.0.CO;2-5 |
| [21] | Szwarc, W., Grosso, A., & Della Croce, F. (2001). Algorithmic paradoxes of the single-machine total tardiness problem. Journal of Scheduling, 4, 93–104. · Zbl 0994.90076 · doi:10.1002/jos.69 |
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.
