Parallel machine scheduling with splitting jobs. (English) Zbl 0962.90020
Summary: The Parallel Machine Scheduling (PMS) problem is to schedule \(n\) jobs on \(m\) parallel machines with the minimum total cost. Generally, there is a hypothesis: a job cannot be processed on two machines simultaneously if preemption is allowed. When the processing requirement of a job is considered as the demand of a product, jobs can be split arbitrarily to continuous sublots and processed independently on \(m\) machines. So, we can discuss PMS under a hypothesis: any part of a job can be processed on two different machines at the same time, and we call it PMS with splitting jobs. In this paper, we first present some simple cases which are polynomial solvable. Furthermore, a heuristic ML and its worst-case analysis are shown for \(P/ \text{split}/ C_{\max}\) with independent job setup times. The worst-case performance ratio of ML is within \(\frac 74- 1/m\) \((m\geq 2)\).
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
parallel machine scheduling; setup times; worst case analysis; parallel machine scheduling (PMS) problem; worst-case analysisReferences:
| [1] | Chen, B., A better heuristic for preemptive parallel machine scheduling with setup times, SIAM J. Comput., 22, 6, 1303-1318 (1993) · Zbl 0806.90061 |
| [2] | Cheng, T. C.E.; Sin, C. C.S., A state-of-the-art review of parallel-machine scheduling research, European J. Oper. Res., 47, 271-292 (1990) · Zbl 0707.90053 |
| [3] | Fisher, M. L., Worst-case analysis of heuristic algorithms, Magt. Sci., 26, 1-17 (1980) · Zbl 0448.90041 |
| [4] | Garey, M. R.; Graham, R. L.; Johnson, D. S., Performance guarantees for scheduling algorithms, Oper. Res., 26, 3-21 (1978) · Zbl 0371.90068 |
| [5] | J.R. Jackson, Scheduling a production line to minimize maximum tardiness, Research Report 43, Management Science Research Project, University for California, Los Angeles, 1955.; J.R. Jackson, Scheduling a production line to minimize maximum tardiness, Research Report 43, Management Science Research Project, University for California, Los Angeles, 1955. |
| [6] | Karmarkar, N., A new polynomial time algorithm for linear programming, Combinatorica, 4, 375-395 (1984) · Zbl 0557.90065 |
| [7] | Lam, K.; Xing, W., New trends in parallel machine scheduling, Internat. J. Oper. Production Management, 17, 326-338 (1997) |
| [8] | E.L. Lawler, Recent results in the theory of machine scheduling, Mathematical Programming the State of the Art - Bonn 1982, Springer, Berlin, 1983, pp. 202-234.; E.L. Lawler, Recent results in the theory of machine scheduling, Mathematical Programming the State of the Art - Bonn 1982, Springer, Berlin, 1983, pp. 202-234. · Zbl 0547.90042 |
| [9] | Lawler, E. L.; Labetoulle, J., On preemptive scheduling of unrelated parallel processors by linear programming, J. Assoc. Comput. Mach., 25, 612-619 (1978) · Zbl 0388.68027 |
| [10] | Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., Sequencing and scheduling: algorithms and complexity, (Grave, S.; Rinnooy Kan, A. H.G.; Zipkin, P., Logistics of Production and Inventory (1993), North-Holland: North-Holland Amsterdam), 445-522 |
| [11] | McNaughton, R., Scheduling with Deadlines and Loss Functions, Management Sci., 6, 1-12 (1959) · Zbl 1047.90504 |
| [12] | Monma, C. L.; Potts, C. N., Analysis of heuristics for preemptive parallel machine scheduling with job setup times, Oper. Res., 41, 5, 981-993 (1993) · Zbl 0795.90034 |
| [13] | Moore, J. M., An \(n\) job, one machine sequencing algorithm for minimizing the number of late jobs, Management Sci., 15, 102-109 (1968) · Zbl 0164.20002 |
| [14] | Potts, C. N.; Van Wassenhove, L. N., Integrating scheduling with batching and lotsizing: a review of algorithms and complexity, J. Oper. Res. Soc., 43, 5, 395-406 (1992) · Zbl 0756.90050 |
| [15] | Serafini, P., Scheduling jobs on several machines with the job splitting property, Oper. Res., 44, 4, 617-628 (1996) · Zbl 0865.90081 |
| [16] | Smith, W. E., Various optimizers for single stage production, Naval Res. Logist. Quart., 3, 59-66 (1956) |
| [17] | Xing, W.; Zhang, J., Splitting parallel machine scheduling (in Chinese), Oper. Res. Trans., 2, 30-41 (1998) |
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.
