Lower bounds and algorithms for flowtime minimization on a single machine with set-up times. (English) Zbl 0966.90031
Summary: We consider the scheduling of \(N\) jobs divided into \(G\) families for processing on a single machine. No set-up is necessary between jobs belonging to the same family. A set-up must be scheduled when switching from the processing of family \(i\) jobs to those of another family \(j\), \(i\neq j\), the duration of this set-up being the sequence-independent set-up time \(s_j\) for family \(j\). We propose lower bounds for the problem of minimizing the weighted flowtime on a single machine with family set-up times and static job availability. These lower bounds are incorporated into a branch-and-bound algorithm which can efficiently solve instances with up to 70 jobs.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Keywords:
scheduling; single machine; family set-up times; static job availability; branch-and-bound algorithmReferences:
| [5] | Sequencing and scheduling: algorithms and complexity. In Handbooks in Operations Research and Management Science, vol. 4. Elsevier: Amsterdam, 1993. |
| [8] | Machine Scheduling Problems: Classification, Complexity and Computations: Nijhoff: The Hague, 1976. |
| [14] | A comparative study of local search methods for one-machine sequencing problems. Ph.D. Thesis, De Nayer Institute, Belgium, 1998. |
| [17] | Genetic algorithms and scheduling problems. Ph.D. Thesis, University of Cambridge, 1992. |
| [18] | Solving the weighted completion time problem with batch setups. Working Paper #98-118, Amos Tuck School of Business Administration, Dartmouth College, 1998. |
| [19] | A study of models and algorithms for machine scheduling problems with setup times. Ph.D. Thesis, University of Melbourne, Australia, 2000. |
| [23] | Production Flow Analysis for Planning Group Technology. Oxford University Press: Oxford, 1989. |
| [25] | Models and algorithms for machine scheduling with setup times. In: Computer Aided and Integrated Manufacturing Systems: Techniques and Applications, (ed.). Gordon & Breach: London, to appear. |
| [30] | Introduction to Sequencing and Scheduling. Wiley: New York, 1974. |
| [31] | Theory of Scheduling. Addison-Wesley: Reading, MA, 1967. |
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.
