Routing Two-Machine Flowshop Problems on Networks with Special Structure

Averbakh, Igor; Berman, Oded
November 1996
Transportation Science;Nov96, Vol. 30 Issue 4, p303
Academic Journal
We consider a version of the routing two-machine flowshop problem, where n jobs located at different nodes of a transportation network must be executed by two machines traveling between the jobs. Each job must be processed by both machines in the order, machine 1 first, machine 2 second. The goal is to minimize the makespan given that the total distance traveled must be as small as possible. Properties of the problem are discussed, and algorithms with complexity O(n log n) are developed for the problem on trees and cactuses.


Related Articles

  • Evaluating Performance of Quality-of-Service Routing in Large Networks. Raghavan, V. Narasimha; Venkatesh, M.; Labbai, T. Peer Meera; Prabhu, Praveen Dwarakanath // Proceedings of World Academy of Science: Engineering & Technolog;2007, Vol. 20, p254 

    The performance and complexity of QoS routing depends on the complex interaction between a large set of parameters. This paper investigated the scaling properties of sourcedirected link-state routing in large core networks. The simulation results show that the routing algorithm, network...

  • AUTOROUTING Completion and Quality. Pfeil, Charles // Printed Circuit Design & Manufacture;Jul2004, Vol. 21 Issue 7, p26 

    Focuses on the quality and completion of autorouting. Comparison between designers and autorouting machines; Ways to measure route quality; Qualities of autorouters that designers want to achieve; Recommendations for productive autorouting.

  • 802.11n: is it worth it?  // Australian PC User;Oct2008, Vol. 20 Issue 10, p38 

    The article provides an answer to a question whether 802.11n is worthwhile as a router.

  • TEST YOUR NETWORK.  // APC (Bauer Media Group);Mar2011, Vol. 31 Issue 3, p79 

    The article presents information on how to check the current network settings to test the system's compatibility with the latest Windows features.

  • The great afterthought: Your broadband router. Tollly, Kevin // Network World;11/20/2006, Vol. 23 Issue 45, p29 

    The article offers instructions on how to gain access to a broadband router.

  • Router Booter.  // Micro Mart;1/9/2014, Issue 1293, p91 

    The article presents an answer to a question regarding the performance of a Belkin router.

  • Gateway-to-Gateway Protocol.  // Network Dictionary;2007, p210 

    An encyclopedia entry for "Gateway-to-Gateway Protocol" is presented. It is a MILNET protocol that defines how core routers or gateways should exchange reachability and routing information. The protocol employs a distributed shortest-path algorithm. The protocol is already obsolete.

  • Preference Location-based Routing in Delay Tolerant Networks. Jieyan Liu; Haigang Gong; Jiazhi Zeng // International Journal of Digital Content Technology & its Applic;Dec2011, Vol. 5 Issue 12, p468 

    Routing in Delay Tolerant Networks (DTNs) is a challenge due to the fact that the network graph is intermittently connected. However, routing benefits considerably if one can take advantage of knowledge concerning nodes mobility, recent studies have shown that human have location visiting...

  • Fast and Scalable IP Address Lookup with Time Complexity of LogmLogm(n). Prakash, Abhishant; Gautam, Alok Sagar // Journal of Advances in Information Technology;May2014, Vol. 5 Issue 2, p58 

    Router is a device which is used to route the incoming data packets from the sender to the destination using the IP address of the destination side. Since the router performs the task in the real time so there are millions and millions of the data packets which the router has to process. The...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics