Exact algorithms for scheduling multiple families of jobs on parallel machines. (English) Zbl 1044.90033
Summary: In many practical manufacturing environments, jobs to be processed can be divided into different families such that a setup is required whenever there is a switch from processing a job of one family to another job of a different family. The time for setup could be sequence independent or sequence dependent. We consider two particular scheduling problems relevant to such situations. In both problems, we are given a set of jobs to be processed on a set of identical parallel machines. The objective of the first problem is to minimize total weighted completion time of jobs, and that of the second problem is to minimize weighted number of tardy jobs. We propose column generation based branch and bound exact solution algorithms for the problems. Computational experiments show that the algorithms are capable of solving both problems of medium size to optimality within reasonable computational time.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Keywords:
parallel machine scheduling; setup times; set partitioning type formulation; column generation; branch and boundReferences:
| [1] | Allahverdi, OMEGA Internat J Management Sci 27 pp 219– (1999) |
| [2] | Barnhart, Oper Res 46 pp 316– (1998) |
| [3] | Chen, INFORMS J Comput 11 pp 78– (1999) |
| [4] | Chen, European J Oper Res 116 pp 220– (1999) |
| [5] | and Theory of scheduling, Addison-Wesley, Reading, MA, 1967. |
| [6] | Dantzig, Oper Res 8 pp 101– (1960) |
| [7] | Desrochers, Oper Res 40 pp 342– (1992) |
| [8] | Dietrich, Ann Oper Res 43 pp 359– (1993) |
| [9] | Ghosh, Oper Res Letters 16 pp 271– (1994) |
| [10] | Kang, Management Sci 45 pp 273– (1999) |
| [11] | and ?Sequencing and scheduling: Algorithms and complexity,? Handbooks in operations research and management science, Volume 4, Logistics of production of inventory, and (Editors), North-Holland, Amsterdam, 1993, pp. 445-522. |
| [12] | Lee, Naval Res Logist 47 pp 145– (2000) |
| [13] | Liaee, Int J Prod Econ 51 pp 165– (1997) |
| [14] | Mehrotra, INFORMS J Comput 8 pp 344– (1996) |
| [15] | Monma, Oper Res 37 pp 798– (1989) |
| [16] | Scheduling: Theory, algorithm, and system, Prentice Hall, Englewood Cliffs, NJ, 1995. |
| [17] | Potts, European J Oper Res 120 pp 228– (2000) |
| [18] | Potts, J Oper Res Soc 43 pp 395– (1992) |
| [19] | Savelsbergh, Oper Res 45 pp 831– (1997) |
| [20] | Vance, Comput Optim Appl 3 pp 111– (1994) |
| [21] | Van den Akker, INFORMS J Comput 12 pp 111– (2000) |
| [22] | Van den Akker, Oper Res 47 pp 862– (1999) |
| [23] | Webster, Comput Oper Res 28 pp 127– (2001) |
| [24] | Webster, Oper Res 43 pp 692– (1995) |
| [25] | Weng, Int J Prod Econ 70 pp 215– (2001) |
| [26] | Integer programming, Wiley, New York, 1998. · Zbl 0930.90072 |
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.
