Top

Journal of Scheduling

Published in:

01-10-2015

Optimal control of a two-server flow-shop network

Authors: Yossef Luzon, Yariv Marmor, Eugene Khmelnitsky

Published in: Journal of Scheduling | Issue 5/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper we suggest a new, intuitive, and simple method for scheduling jobs in a two-server flow-shop network (FSN) with the minimum makespan objective. Multiple types of jobs with corresponding constant service times arrive at the network at various times over a finite time interval. An analog fluid network is proposed and its optimal fluid control policy determined. We make use of this optimal control policy to suggest a new method for scheduling jobs in the original discrete FSN and prove its asymptotic optimality. The method is particularly attractive because it falls into the class of easy-to-implement and computationally inexpensive on-line algorithms. Numerical simulations are used to evaluate the performance of the suggested method and show that it performs optimally in almost all simulated instances. Some additional properties of the network are discussed and illustrated.

previous article Decentralized subcontractor scheduling with divisible jobs

next article Optimal control strategies for single-machine family scheduling with sequence-dependent batch setup and controllable processing times

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Athans, M., & Falb, P. (1966). Optimal control. New York: McGraw-Hill.

Avram, F., Bertsimas, D., & Ricard, M. (1995). Fluid models of sequencing problems in open queueing networks: An optimal control approach. In F. P. Kelly & R. J. Williams (Eds.), Stochastic networks. Proceedings of the International Mathematics Association (Vol. 71, pp. 199–234). New York: Springer.CrossRef

Bai, D., Huo, M., & Tang, L. (2008). A new lower bound for flow shop makespan with release dates. In IEEE International Conference on Service Operations and Logistics, and Informatics IEEE Xplore, Vol. 1 (pp. 276–280).

Becker, C., & Scholl, A. (2006). A survey on problems and methods in generalized assembly line balancing. European Journal of Operations Research, 168(3), 694–715.CrossRef

Bertsekas, D. P. (1995). Dynamic programming and optimal control (Vol. 1). Belmont, MA: Athena Scientific.

Bertsimas, D., & Gamarnik, D. (1999). Asymptotically optimal algorithm for job shop scheduling and packet routing. Journal of Algorithms, 33, 296–318.CrossRef

Bertsimas, D., & Sethuraman, J. (2002). From fluid relaxations to practical algorithms for job shop scheduling: The makespan objective. Mathematical Programming, 92(1), 61–102.CrossRef

Bertsimas, D., Gamarnik, D., & Tsitsiklis, N. (1996). Stability conditions for multiclass fluid queueing networks. IEEE Transactions on Automatic Control, 41(11), 1618–1631.CrossRef

Bryson, A. E., & Ho, Y. C. (1975). Applied optimal control. New York: Hemisphere Publishing.

Chen, H., & Yao, D. D. (1993). Dynamic scheduling of a multiclass fluid network. Operations Research, 41(6), 1104–1115.CrossRef

Emmons, H., & Vairaktarakis, G. (2013). Flow shop scheduling: Theoretical results, algorithms and appllications. International Series in Operations Research and Management Science (Vol. 182). New Yok: Springer.

Haji, R., & Newell, G. (1971). Optimal strategies for priority queues with nonlinear costs of delay. SIAM Journal on Applied Mathematics, 20, 224–240.CrossRef

Hall, L. A. (1994). A polynomial time approximation scheme for a constrained flow-shop scheduling problem. Mathematics of Operation Research, 19, 68–85.CrossRef

Hall, L. A. (1998). Approximability of flow shop scheduling. Mathematical Programming, 82, 175–190.

Johnson, S. M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1, 61–67.CrossRef

Kaminsky, P., & Simchi-Levi, M. (2001). Asymptotic analysis of an on-line algorithm for the single machine completion time problem with release dates. Operations Research Letters, 29, 141–148.CrossRef

Kashyrskikh, K. N., Potts, C., & Sevastianov, S. (2001). A 3/2-approximation algorithm for two-machine flow-shop sequencing subject to release dates. Discrete Applied Mathematics, 114(1), 255–271.CrossRef

Kebarighotbi, A., & Cassandras, CG. (2009). Revisiting the optimality of the \(c\mu \)-rule with stochastic flow models. In Proceedings of the 48th IEEE Conference on Decision and Control, held jointly with the 28th Chinese Control Conference (CDC/CCC) (pp. 2304–2309). Shanghai: IEEE.

Lenstra, J. K., Kan, A. R., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Operations Research, 1, 343–362.

Luo, X., & Bertsimas, D. (1999). A new algorithm for state-constrained separated continuous linear programs. SIAM Journal on Control and Optimization, 37, 177210.

Luzon, Y. (2010). Fluid based resource allocation and appointment scheduling system and method PPA No. 61/089,120 App No US13/958,743, EP09168021.5, IL200425.

Luzon, Y., Penn, M., & Mandelbaum, A. (2009). Scheduling appointments via fluids control. In International Conference on Model-Based Systems Engineering (MBSE ’09) (pp. 29–35). Israel: IEEE.

Luzon, Y., Marmor, Y., & Khmelnitsky, E. (2012). An optimal control policy for a tandem queueing network. In 12th Viennese Workshop Optimal Control, Dynamic Games and Nonlinear Dynamics, ORCOS, Institute of Mathematical Methods in Economics, Vienna University of Technology, Vienna, Austria.

Maimon, O., Khmelnitsky, E., & Kogan, K. (1998). Optimal flow control in manufacturing systems: Production planning and scheduling. Dordrecht: Kluwer Academic Publishers.CrossRef

Meyn, S. P. (2008). Control techniques for complex networks. New York: Cambridge University Press.

Mieghem, J. A. V. (1995). Dynamic scheduling with convex delay costs: The generalized \(c\mu \) rule. Annals of Applied Probability, 5, 809–833.CrossRef

Mönch, L., Fowler, J. W., Dauzère-Pérès, S., Mason, S. J., & Rose, O. (2011). A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations. Journal of Scheduling, 14(6), 583–599.CrossRef

Nazarathy, Y., & Weiss, G. (2010). A fluid approach to large volume job shop scheduling. Journal of Scheduling, 13(5), 509–529.CrossRef

Pinedo, M. (2009). Planning and scheduling in manufacturing and services. Springer series in operations research (2nd ed.). New York: Springer.CrossRef

Pinedo, M. (2012). Scheduling: Theory, algorithms and systems (4th ed.). New York: Springer.CrossRef

Potts, C. N. (1985). Analysis of heuristics for two-machine flow-shop sequencing subject to release dates. Mathematics of Operation Research, 10, 576–584.CrossRef

Pullan, M. C. (1993). An algorithm for a class of continuous linear programs. SIAM Journal on Control and Optimization, 31, 1558–1577.CrossRef

Pullan, M. C. (1994). On the solution of a class of continuous linear programs. SIAM Journal on Control and Optimization, 32, 1289–1296.CrossRef

Pullan, M. C. (1995). Form of optimal solutions for separated continuous linear programs. SIAM Journal on Control and Optimization, 33(6), 1952–1977.CrossRef

Sethi, S., & Thompson, G. (2000). Optimal control theory: Applications to management science and economics (2nd ed.). Boston: Kluwer Academic Publishers.

Smith, W. E. (1956). Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3(1–2), 59–66.CrossRef

Talwar, P. P. (1967). A note on sequencing problems with uncertain job times. Journal of the Operations Research Society of Japan, 47, 93–97.

Yu, W., Hoogeveen, H., & Lenstra, J. K. (2004). Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard. Journal of Scheduling, 7(5), 333–348.CrossRef

Title: Optimal control of a two-server flow-shop network
Authors: Yossef Luzon
Yariv Marmor
Eugene Khmelnitsky
Publication date: 01-10-2015
Publisher: Springer US
Published in: Journal of Scheduling / Issue 5/2015
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-015-0439-8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 5/2015

Improved rolling horizon approaches to the aircraft sequencing problem

On contiguous and non-contiguous parallel task scheduling

Interval scheduling and colorful independent sets

Optimal control strategies for single-machine family scheduling with sequence-dependent batch setup and controllable processing times

A two-stage coupled algorithm for an integrated maintenance planning and flowshop scheduling problem with deteriorating machines

Decentralized subcontractor scheduling with divisible jobs

Premium Partner