Network Models and Optimization

Many real-world problems from operations research (OR) / management science (MS) are very complex in nature and quite hard to solve by conventional optimization techniques. Since the 1960s there has been being an increasing interest in imitating living beings to solve such kinds of hard optimization problems. Simulating natural evolutionary processes of human beings results in stochastic optimization techniques called evolutionary algorithms (EAs) that can often outperform conventional optimization methods when applied to difficult real-world problems. EAs mostly involve metaheuristic optimization algorithms such as genetic algorithms (GA) [1, 2], evolutionary programming (EP) [3], evolution strategys (ES) [4, 5], genetic programming (GP) [6, 7], learning classifier systems (LCS) [8], swarm intelligence (comprising ant colony optimization (ACO) [9] and particle swarm optimization (PSO) [10, 11]). Among them, genetic algorithms are perhaps the most widely known type of evolutionary algorithms used today.

Network design is one of the most important and most frequently encountered classes of optimization problems [1]. It is a combinatory field in graph theory and combinatorial optimization. A lot of optimization problems in network design arose directly from everyday practice in engineering and management: determining shortest or most reliable paths in traffic or communication networks, maximal or compatible flows, or shortest tours; planning connections in traffic networks; coordinating projects; and solving supply and demand problems. Furthermore, network design is also important for complexity theory, an area in the common intersection of mathematics and theoretical computer science which deals with the analysis of algorithms. However, there is a large class of network optimization problems for which no reasonable fast algorithms have been developed. And many of these network optimization problems arise frequently in applications. Given such a hard network optimization problem, it is often possible to find an efficient algorithm whose solution is approximately optimal. Among such techniques, the genetic algorithm (GA) is one of the most powerful and broadly applicable stochastic search and optimization techniques based on principles from evolution theory.

With the development of economic globalization and extension of worldwide electronic marketing, global enterprise services supported by universal supply chain and world-wide logistics become imperative for the business world. How to manage logistics system efficiently thas hus become a key issue for almost all of the enterprises to reduce their various costs in today’s keenly competitive environment of business, especially for many multinational companies. Today’s pervasive internet and full-fledged computer aided decision supporting systems (DSS) certainly provide an exciting opportunity to improve the efficiency of the logistics systems. A great mass of research has been done in the last few decades. However, weltering in giving perfect mathematical representations and enamored with developing various type of over-intricate techniques in solution methods, most researchers have neglected some practical features of logistics. In this chapter, the logistics network models are introduced, consolidating different aspects in practical logistics system. A complete logistics system covers the entire process of shipping raw materials and input requirements from suppliers to plants, the conversion of the inputs into products at certain plants, the transportation of the products to various warehouse of facilities, and the eventual delivery of these products to the final customers. To manage the logistics system efficiently, the dynamic and static states of material flows – transportation and storage – are key points that we need to take into consideration.

Modeling and design of large communication and computer networks have always been an important area to both researchers and practitioners. The interest in developing efficient design models and optimization methods has been stimulated by high deployment and maintenance costs of networks, which make good network design potentially capable of securing considerable savings. For many decades, the area of network design had been relatively stable and followed the development of telephone networks and their smooth transition from analog to digital systems. In the past decade, however, networks have undergone a substantial change caused by the emergence and rapid development of new technologies and services, an enormous growth of traffic, demand for service availability and continuity, and attempts to integrate new networking and system techniques and different types of services in one network. As a consequence, today’s network designers face new problems associated with diverse technologies, complicated network architectures, and advanced resource and service protection mechanisms.

Advanced planning and scheduling (APS) refers to a manufacturing management process by which raw materials and production capacity are optimally allocated to meet demand. APS is especially well-suited to environments where simpler planning methods cannot adequately address complex trade-offs between competing priorities. However, most scheduling problems of APS in the real world face inevitable constraints such as due date, capability, transportation cost, set up cost and available resources. Generally speaking, we should obtain an effective “flexibility” not only as a response to the real complex environment but also to satisfy all the combinatorial constraints. Thus, how to formulate the complex problems of APS and find satisfactory solutions play an important role in manufacturing systems.

From ancient times to the modern day, the concept of assembly has naturally been changed a lot. The most important milestone in assembly is the invention of assembly lines (ALs). In 1913, Henry Ford completely changed the general concept of assembly by introducing ALs in automobile manufacturing for the first time. He was the first to introduce a moving belt in a factory, where the workers were able to build the famous model-T cars, one piece at a time instead of one car at a time. Since then, the AL concept revolutionized the way products were made while reducing the cost of production. Over the years, the design of efficient assembly lines received considerable attention from both companies and academicians. A well-known assembly design problem is assembly line balancing (ALB), which deals with the allocation of the tasks among workstations so that a given objective function is optimized.

Recent advances in computing, storage, and communication technologies have made a wide variety of multimedia applications possible. Multimedia systems combine a various information sources, such as audio, video, text, graphics and image, into the wide range of application (Chen, 1996). Video and audio data are referred to as continuous media due to their real-time delivery requirements, whereas text, graphics and image data are referred to as discrete media. Since continuous media are displayed within a certain time constraint, their computation and manipulation of continuous media should be handled under more limited condition than that of discrete media. The objective of the task scheduling models is to minimize total tardiness and the scheduling these tasks on multiprocessor system is NP-hard problem. A continuous task scheduling, real-time task scheduling on homogeneous system and real-time task scheduling on heterogeneous system are introduced in this chapter.

Everywhere we look in our daily lives, networks are apparent. National highway systems, rail networks, and airline service networks provide us with the means to cross great geographical distances to accomplish our work, to see our loved ones, and to visit new places and enjoy new experiences. Manufacturing and logistics networks give us access to life’s essential foodstock and to consumer products. And computer networks, such as airline reservation systems, have changed the way we share information and conduct our business and personal lives. In all of these problem domains, and in many more, we wish to move some entity (electricity, a product, a person or a vehicle, a message) from one point to another in an underlying network, and to do so as efficiently as possible, both to provide good service to the users of the network and to use the underlying (and typically expensive) transmission facilities effectively. In the most general sense, we want to learn how to model application settings as mathematical objects known as network design models and to study various ways (algorithms) to solve the resulting models [1]. In this chapter, the following advanced network models are introduced as shown in Fig. 9.1.