×

A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows. (English) Zbl 1161.90007

Summary: This paper deals with several bicriteria open-shop scheduling problems where jobs are pre-emptable and their corresponding time-windows must be strictly respected. The criteria are a performance cost and the makespan. Network flow approaches are used in a lexmin procedure with a bounded makespan and the considered bicriteria problems are solved. Finally, the computational complexity of the algorithm and a numerical example are reported.

MSC:

90B35 Deterministic scheduling theory in operations research
90B15 Stochastic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R. K.; Goldberg, A. V.; Orlin, J. B.; Tarjan, R. E., Finding minimum-cost flows by double scaling, Mathematical Programming, 53, 243-266 (1992) · Zbl 0761.90036
[2] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows (1993), Prentice-Hall Inc., (Chapter 11) · Zbl 1201.90001
[3] Chen, Y. L., Scheduling jobs to minimize total cost, European Journal of Operational Research, 74, 111-119 (1994) · Zbl 0802.90058
[4] Chen, Y. L., A parametric maximum flow algorithm for bipartite graphs with applications, European Journal of Operations Research, 80, 226-235 (1995) · Zbl 0928.90006
[5] Cho, Y.; Sahni, S., Preemptive scheduling of independent jobs with release and due times on open, flow and job shops, Operations Research, 29, 511-522 (1981) · Zbl 0455.90043
[6] Federgruen, A.; Groenevelt, H., Preemptive scheduling of uniform machines by ordinary network flow techniques, Management Science, 32, 3, 341-349 (1986) · Zbl 0603.90071
[7] Gallo, G.; Grigoriadis, M. D.; Tarjan, R. T., A fast parametric maximum flow algorithm and applications, SIAM Journal of Computing, 18, 1, 30-55 (1989) · Zbl 0679.68080
[8] A.V. Goldberg, R.E. Tarjan, 1986. A new approach to the maximum flow problem, in: Proceedings of the 18th ACM Symposium on the Theory of Computation, 1986, pp. 136-146.; A.V. Goldberg, R.E. Tarjan, 1986. A new approach to the maximum flow problem, in: Proceedings of the 18th ACM Symposium on the Theory of Computation, 1986, pp. 136-146.
[9] Goldberg, A. V.; Tarjan, R. E., Solving minimum cost flow problem by successive approximation, Mathematics of Operations Research, 15, 430-466 (1990) · Zbl 0727.90024
[10] T. González, A note on open shop preemptive schedules, Technical Report No. 214, Computer Science Dept., Pennsylvania State University, 1976.; T. González, A note on open shop preemptive schedules, Technical Report No. 214, Computer Science Dept., Pennsylvania State University, 1976.
[11] González, T.; Sahni, S., Open shop scheduling to minimize finish time, Journal of the Association Computing Machine, 23, 665-679 (1976) · Zbl 0343.68031
[12] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044
[13] Knuth, D. E., The Art of Computer Programming, Sorting and Searching, vol. 3 (1998), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0191.17903
[14] Lawler, E. L.; Labetoulle, J., On preemptive scheduling of unrelated parallel processors by linear programming, Journal of the Association Computing Machine, 25, 612-619 (1978) · Zbl 0388.68027
[15] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D., Sequencing and scheduling: Algorithms and complexity, (Graves, S. C.; Rinnooy Kan, A. H.G.; Zipkin, P. H., Handbooks in Operations Research and Management Science, vol. 4 (1993), North Holland), (Chapter 9) · Zbl 0482.68035
[16] McCormick, S. T., Fast algorithms for parametric scheduling come from extensions to parametric maximum flow, Operations Research, 47, 5, 744-756 (1999) · Zbl 0982.90023
[17] Orlin, J. B., A faster strongly polynomial minimum cost flow algorithm, Operations Research, 41, 2, 338-350 (1993) · Zbl 0781.90036
[18] Pinedo, M., Scheduling: Theory, Algorithms and Systems (2002), Prentice-Hall Inc. · Zbl 1145.90394
[19] Sedeño-Noda, A.; Alcaide, D.; González-Martı´n, C., Network flow approaches to pre-emptive open-shop scheduling problems with time-windows, European Journal of Operational Research, 174, 3, 1501-1518 (2006) · Zbl 1103.90048
[20] A. Sedeño-Noda, C. González-Martı´n, On the three-index transportation problem (in Spanish), Working paper, 2007.; A. Sedeño-Noda, C. González-Martı´n, On the three-index transportation problem (in Spanish), Working paper, 2007.
[21] Serafini, P., Scheduling jobs on several machines with the job splitting property, Operations Research, 44, 4, 617-628 (1996) · Zbl 0865.90081
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.