Scheduling two-machine no-wait open shops to minimize makespan. (English) Zbl 1071.90018
Summary: This paper examines the problem of scheduling two-machine no-wait open shops to minimize makespan. The problem is known to be strongly NP-hard. An exact algorithm, based on a branch-and-bound scheme, is developed to optimally solve medium-size problems. A number of dominance rules are proposed to improve the search efficiency of the branch-and-bound algorithm. An efficient two-phase heuristic algorithm is presented for solving large-size problems. Computational results show that the branch-and-bound algorithm can solve problems with up to 100 jobs within a reasonable amount of time. For large-size problems, the solution obtained by the heuristic algorithm has an average percentage deviation of 0.24% from a lower bound value.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and schedulinga survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044 |
| [2] | Hall, N. G.; Sriskandarajah, C. A., Survey of machine scheduling problems with blocking and no-wait in process, Operations Research, 44, 510-525 (1996) · Zbl 0864.90060 |
| [3] | Goyal, S. K.; Sriskandarajah, C., No-wait shop schedulingcomputational complexity and approximate algorithms, Operation Research, 25, 220-244 (1988) · Zbl 0661.90045 |
| [4] | Gilmore, P. C.; Gomory, R. E., Sequencing a one state-variable machinea solvable case of the traveling salesman problem, Operations Research, 12, 655-679 (1964) · Zbl 0126.36006 |
| [5] | Rock, H., The three machine no-wait flowshop problem is NP-complete, Journal of the Associated Computing Machinery, 31, 336-345 (1984) · Zbl 0632.68038 |
| [6] | Piehler, J., Ein beitrag zum reinhenfolgeproblem, Unternehmensforschung, 4, 138-142 (1960) |
| [7] | Reddi, S. S.; Ramamoorthy, C. V., On the flowshop sequencing problems with no wait in process, Operational Research Quarterly, 23, 323-331 (1972) · Zbl 0238.90080 |
| [8] | Wismer, D. A., Solution of the flowshop sequencing problem with no intermediate queues, Operations Research, 20, 689-697 (1972) · Zbl 0241.90031 |
| [9] | Gangadharan, R.; Rajendran, C., Heuristic algorithms for scheduling in the no-wait flowshop, International Journal of Production Economics, 32, 285-290 (1993) |
| [10] | Rajendran, C., A no-wait flowshop scheduling heuristic to minimize makespan, Journal of the Operational Research Society, 45, 472-478 (1994) · Zbl 0799.90060 |
| [11] | Aldowaisan, T.; Allahverdi, A., New heuristics for no-wait flowshops to minimize makespan, Computers and Operations Research, 30, 1219-1231 (2003) · Zbl 1047.90053 |
| [12] | Coffman, E. G.; Graham, R. L., Optimal scheduling for two-processor systems, Acta Informatica, 1, 200-213 (1972) · Zbl 0248.68023 |
| [13] | Ullman, J. D., NP-complete scheduling problems, Journal of Computer and System Science, 10, 384-393 (1975) · Zbl 0313.68054 |
| [14] | Gonzales, T., Unit execution time shop problems, Mathematics of Operations Research, 7, 57-66 (1982) · Zbl 0499.90047 |
| [15] | Brucker, P.; Jurisch, B.; Jurisch, M., Openshop problems with unit time operations, Zeitschrift fur Operations Research, 37, 1, 59-73 (1993) · Zbl 0776.90033 |
| [16] | Sahni, S.; Cho, Y., Complexity of scheduling shops with no-wait in process, Mathematics of Operations Research, 4, 448-457 (1979) · Zbl 0438.90039 |
| [17] | Sidney, J. B.; Sriskandarajah, C., A heuristic for the two-machine no-wait openshop scheduling problem, Naval Research Logistics, 46, 129-145 (1999) · Zbl 0922.90091 |
| [18] | Yao, M. J.; Soewandi, H., Simple heuristics for the two machine openshop problem with blocking, Journal of the Chinese Institute of Industrial Engineers, 17, 5, 537-547 (2000) |
| [19] | Yao MJ, Lai CW. A genetic algorithm for the two machine openshop scheduling problem with blocking. The Second Japanese-Sino Optimization Meeting (JSOM 2002), Kyoto, Japan, September 25-27.; Yao MJ, Lai CW. A genetic algorithm for the two machine openshop scheduling problem with blocking. The Second Japanese-Sino Optimization Meeting (JSOM 2002), Kyoto, Japan, September 25-27. |
| [20] | Kuhn, H. W., The Hungarian method for the assignment problem, Naval Research Logistics Quarterly, 2, 83-97 (1955) · Zbl 0143.41905 |
| [21] | Munkres, J., Algorithms for the assignment and transportation problems, SIAM Journal on Applied Mathematics, 5, 32-38 (1957) · Zbl 0083.15302 |
| [22] | Gonzales, T.; Sahni, S., Open shop scheduling to minimize finish time, Journal of the Associated Computing Machinery, 23, 4, 665-679 (1976) · Zbl 0343.68031 |
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.
