Two-machine flowshop scheduling to minimize total tardiness
Authors:
- 1 April 1997
- journal article
- research article
- Published by Taylor & Francis in International Journal of Systems Science
- Vol. 28 (4) , 405-414
Abstract
In this paper, the problem of sequencing jobs on a two-machine flowshop to minimize total tardiness is considered, and a branch-and-bound algorithm is developed. Five dominance properties for the precedence relations between jobs in an optimal solution are proposed and a sharp lower bound on the total tardiness of a subproblem is derived. The dominance properties and the lower bound are implemented in the branch-and-bound algorithm to facilitate the search for an optimal schedule. Computational experiments are conducted and the results show that this algorithm is more efficient than the existing ones.Keywords
This publication has 13 references indexed in Scilit:
- The two-machine flowshop scheduling problem with total tardinessComputers & Operations Research, 1989
- A decomposition algorithm for the single machine total tardiness problemOperations Research Letters, 1982
- Dynamic Programming Solution of Sequencing Problems with Precedence ConstraintsOperations Research, 1978
- Four simple heuristics for scheduling a flow-shopInternational Journal of Production Research, 1978
- The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine SchedulingOperations Research, 1978
- Finding an Optimal Sequence by Dynamic Programming: An Extension to Precedence-Related TasksOperations Research, 1978
- A dual algorithm for the one-machine scheduling problemMathematical Programming, 1976
- Minimizing Total Costs in One-Machine SchedulingOperations Research, 1975
- One-Machine Sequencing to Minimize Certain Functions of Job TardinessOperations Research, 1969
- Optimal two‐ and three‐stage production schedules with setup times includedNaval Research Logistics Quarterly, 1954