Batch-size-based rearrangement of the shop floor into mini-lines. (English) Zbl 1356.90054
Summary: We study the allocation of machines in a job shop environment to groups of jobs so as to obtain a collection of disjoint production lines minimising the overall cycle time. Jobs are often grouped according to similarities based on functionality or production process, but in some settings it makes more sense to group jobs according to batch size to exploit differences in setup and run times among technologies and machine types. We formulate a model to find an optimal group partition of jobs and an optimal assignment of machines to groups. We show that the problem is \(\mathcal{NP}\)-hard and formulate a heuristic based on genetic algorithms to find approximate solutions.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
manufacturing processes; production flow analysis; scheduling; batch processing; batch schedulingSoftware:
GenocopReferences:
| [1] | DOI: 10.1287/opre.41.4.641 · doi:10.1287/opre.41.4.641 |
| [2] | DOI: 10.1287/opre.39.1.42 · Zbl 0742.90033 · doi:10.1287/opre.39.1.42 |
| [3] | DOI: 10.1287/opre.40.4.750 · Zbl 0758.90042 · doi:10.1287/opre.40.4.750 |
| [4] | Conway R, Theory of scheduling (1967) |
| [5] | Dietrich B, Annals of Operations Research 43 pp 359– (1993) |
| [6] | DOI: 10.1016/j.cie.2003.11.004 · doi:10.1016/j.cie.2003.11.004 |
| [7] | Garey MR, Computers and intractability: A guide to the theory of NP-completeness (2002) |
| [8] | Graham RL, Concrete mathematics: A foundation for computer science,, 2. ed. (1994) · Zbl 0836.00001 |
| [9] | DOI: 10.1080/00207549308956810 · doi:10.1080/00207549308956810 |
| [10] | DOI: 10.1080/00207549608904988 · Zbl 0927.90033 · doi:10.1080/00207549608904988 |
| [11] | DOI: 10.1016/j.ejor.2006.07.023 · Zbl 1128.90028 · doi:10.1016/j.ejor.2006.07.023 |
| [12] | DOI: 10.1287/opre.40.4.764 · Zbl 0759.90046 · doi:10.1287/opre.40.4.764 |
| [13] | Michalewicz Z, Genetic algorithms + data structures=evolution programs,, 3. ed. (1999) · Zbl 0841.68047 |
| [14] | DOI: 10.1016/S0925-5273(99)00051-1 · doi:10.1016/S0925-5273(99)00051-1 |
| [15] | DOI: 10.1016/S0377-2217(99)00153-8 · Zbl 0953.90028 · doi:10.1016/S0377-2217(99)00153-8 |
| [16] | DOI: 10.1080/00207540500066762 · Zbl 1068.90063 · doi:10.1080/00207540500066762 |
| [17] | DOI: 10.1016/j.ijpe.2004.04.013 · doi:10.1016/j.ijpe.2004.04.013 |
| [18] | DOI: 10.1016/j.ejor.2006.01.042 · Zbl 1163.90508 · doi:10.1016/j.ejor.2006.01.042 |
| [19] | Salvador MS, In: Symposium on the theory of scheduling and its applications pp 83– (1973) |
| [20] | Shapiro R(Donner Company), Harvard Business School case (1998) |
| [21] | DOI: 10.1016/0377-2217(90)90295-M · Zbl 0706.90035 · doi:10.1016/0377-2217(90)90295-M |
| [22] | DOI: 10.1080/00207549408957026 · Zbl 0906.90095 · doi:10.1080/00207549408957026 |
| [23] | DOI: 10.1016/j.cor.2004.04.002 · Zbl 1071.90021 · doi:10.1016/j.cor.2004.04.002 |
| [24] | DOI: 10.1016/j.cor.2005.11.019 · Zbl 1185.90100 · doi:10.1016/j.cor.2005.11.019 |
| [25] | DOI: 10.1287/opre.36.3.445 · Zbl 0646.90039 · doi:10.1287/opre.36.3.445 |
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.
