Economics of built to order, BTO, or production for final demand: What types of products are candidates for BTO?
Products that have been made BTO for some time are restaurant meals, airplanes, ships, heavy equipment by Caterpiller, firetrucks, some golf clubs. Products that are not made BTO are argricultural products and most clothes.
In the renaissance in American manufacturing starting in the mid 1980s, US firms imitated the Japanese innovations. For example, Chrysler created Japanese style design teams to greatly accelerate the design of new cars. Firms in the US became converts to quality control as they discovered that consumers preferred quality Japanese products.
The US firms exploited their lead in software to innovate in production in beyond the Japanese approach. Because US suppliers are generally not near the assemblylines US reduction in inventory and work in progress was promoted by software programs starting with material resource planning, MRP and advancing to supply chain management software programs of today. Because US supplier firms are generally not adjacent to the assembly plant it is not possible to reduce inventory to the Japanese levels because of the possibility of transportation mishaps. Firms like Dell have their suppliers keeps supplies adjacent to the Dell assembly area and pay for supplies as they are used, McWilliams(1999). In some cases the supplier's 18 wheeler rig is parked at the factory.
Using their lead in software, American firms made innovations culminating the extension of production for final demand for new classes of products. The application of software to soft as opposed to hard automation increased the trend for rapid changeover from one product to another at lower cost. One example is the use of industrial bar codes to simplify the machine intelligence problem of having each machine perform the correct procedure in assemblylines with multiple products. Another example is the software controlled flexible manufacturing system. Another is factory simulation programs created by Aspen Technology (1999), Dassault Systemes (1999), and Tecnomatix (1999) that allow industrial engineers to simulate the factory organization. Use of factory simulation can greatly reduce changeover times, not just of a single machine but an entire factory. In the auto industry the use of factory simulation programs has the promise of reducing the changeover in product production from 8 weeks to 48 hours, see Ross(1998). With soft automation the cost of batch production is falling to the level of previous mass production so that firms under the aegis of total quality management of pleasing the customer are increasingly producing for niche markets.
The culmination in the production for final demand comes about by the use of advances in communication for sales. Dell is one of the first firms to produce products exclusively for final demand and not inventory. At first customers ordered their build to specifications computers via the telephone. Then with the advance of E-commerce on the internet, Dell began selling through the Internet Their software is developed so that it aids the customer in choosing the most appropriate computer for their needs and allows the customer to follow their order through the production and delivery process. In the 21st century we forecast that production for final demand will become a increasingly common manufacturing practice. Remember some manufacturing may always be more suited to production for inventory than production for final demand. But, after starting BTO in computers, Dell is moving away from the concept by trying to sell its production facilities.
In the later part of the 20th century the US government has many steps to promote invention and innovation in manufacturing. One example, is funding for Sematech (1999), a consortium promoting integrated circuit production. The Defense Advanced Research Projects Agency, DARPA (1999), funds numerous inventive and innovative activities in military production that frequently also have broad applications in the private sector such as Agile Manufacturing promoting lean manufacturing and rapid changeover. The Department of Commerce has initiated the manufacturing extension partnership, MEP (1999), to promote innovation and imitation in small firm manufacturing.
The production that could be produced BTO is transportation vehicles such as cars and pickups. Dealerships in the US have lobbied state legislatures so that consumers can not buy vehicles directly from manufacturers, but most go through a dealer. This reduces the profitability of switching to BTO. In the EU there is talk of building vehicles in 5 days that would set the stage for BTO production.
Production for final demand
The innovations leading to production for final demand in firms producing multiple products create a difficult scheduling problem of operating factories shifting from one product to another satisfying customer demands, minimizing inventory and at the same time fully utilizing the production resources. In their most general form, a resource-constrained scheduling problem asks the following question: given a set of tasks, a set of resources and constraints and a measure of performance, what is the best way to assign the resources to the tasks such that the performance is maximized. Formally operation researchers have devised a variety of formal models of industrial scheduling problems such as varying in such factors as the types of machines, their operations, delays, information flows, deterministic or stochastic elements, for example see Dorn and Froeschl(1993).
Planning and scheduling have profound importance for projects consisting of several tasks and constraints associated with them. On a factory floor, determining which jobs to execute in what order on which machines and which employees to assign to a certain job, can mean the difference between profit and loss. Even for relatively small projects, however, the number of possible courses of action quickly become so overwhelming that it becomes almost impossible to achieve an optimum solution. In general, scheduling problems are NP-hard i.e. no algorithm exists that can find optimal solutions to these problems in polynomial time. Heuristics exists for solving exactly some forms of the problem but typically they become intractable(i.e. take more than polynomial time) when additional constraints are added or the problem size grows. As a result, most research has been focussed on either simplifying the scheduling problem(mostly by making assumptions) to the point that it is solvable by some algorithm within reasonable time limits or devising efficient heuristics for finding acceptable (not necessarily optimal) solutions.
In this section, we will briefly discuss the advancements in scheduling and the resulting performance gains. The point to note here is that a scheduling problem with reasonable number of tasks is usually so complex that the most sophisticated scheduling heuristics and fastest machines do not give us the optimum solutions- they only give us better solutions. Usually a move from one scheduling paradigm to the other involves huge investments in time and money and has profound impact on the functioning of firms and of the economy as a whole.
Although the roots of the scheduling problem can be traced back to prehistoric times, active research in this field began with the creation of digital computing machines after 1950. Linear Programming became the first formulation of scheduling problems with the invention of the Simplex algorithm by Dantzig in 1947 that provided efficient computation. Other important early Operations Research methodologies were Monte Carlo simulation techniques, stochastic optimization, queuing theory, Integer Programming (Gomory, 1958), Dynamic Programming, Bellman et al.(1982) and a several combinatorial methods, notably, Balas, (1969) and Branch-and-Bound methods, e.g. Land and Doig, (1960), Little et al., (1963), Barker and McMahon, (1985).
The principles and method of dynamic programming were first elaborated by Bellman in 1950s. For combinatorial scheduling problems, dynamic programming algorithms have exponential computational complexity because in order to calculate the optimal criterion value for any subset of size p, we have to know the criterion values for each subset of size k-1. Thus, for a set of n elements, we have to consider 2n subsets. The branch and bound algorithms divide the problem into several subproblems and calculates the lower bound for each of the subproblems. This procedure usually generates a huge tree. The computational complexity of a branch and bound algorithm is also exponential. Branch and bound methods are therefore limited to less than one hundred activities or even fewer in the multi-model cases. Other enumerative methods also suffer from the exponential computational complexity for reasonably large problems.
Unfortunately most scheduling problems especially the most relevant ones belong to the class of NP-complete problems which are intractable since nobody has shown that a polynomial bounded algorithm exists for these problems. Exact solution methods are thus of limited practical relevance in obtaining better performance.
With the complexity theory developed in computer sciences,Edmonds (1965), Cook (1971) and Karp, (1972), the focus of research shifted from exact but intractable methods to approximate but tractable solutions. Interest in heuristic reasoning within computer sciences was prompted by outstanding researchers like Herbert A. Simon starting in the 1960s. Heuristic search tries to enumerate combinatorial search spaces efficiently by ruling out the areas with low subjective probability of containing an optimal solution. This application of the research in neuro-science and human symbol processing to computer science gave a strong boost to the field of artificial intelligence. Soon the techniques developed in artificial intelligence were being used to find better solutions for real world scheduling problems.
This class of methods comprises several related algorithms. Simulated annealing was proposed as a framework for the solution of combinatorial optimization problems by Kirkpatrick, Gelatt and Vecchi (1983) and independently by Cerny (1985). As the name suggests, the inspiration for this method comes from the Physics of cooling solids. "Simulated annealing allows the allows the algorithms to 'escape' from bad local optima by performing occasional cost-increasing changes. " Lewis and Papadimitriou (1998). Simulated annealing gives good approximations of the optimal in many cases. However the cost-increasing changes often result in great loss of efficiency.
Tabu search, a discrete version of simulated annealing, is a general framework, which was originally proposed by Glover and subsequently expanded in a series of papers. One of the central ideas in this proposal is to guide deterministically the local search process out of local optima (in contrast with the non-deterministic approach of simulated annealing). This can be done using different criteria, which ensure that the loss incurred in the value of the objective function in such an 'escaping' step (a move) is not too important, or is somehow compensated for. " Blazewicz, Ecker, Pesch, Schmidt and Weglarz (1996).
Genetic algorithms are inspired by the theory of evolution; they date back to the early work described in Rechenberg (1973). "They have been designed as general search strategies and optimization methods working on populations of feasible solutions." Blazewicz et al. (1996) The traditional genetic algorithms have often not been suitable for combinatorial optimization problems because of the difficulty in the representation of the solution. Several improvements have therefore been proposed. Local search heuristics or genetic enumeration have compensated for this drawback.
Evolutionary techniques like genetic algorithms and neural nets and other recent techniques like fuzzy logic are mainly being used in rule-based reasoning and expert systems. Due to the early success of evolutionary algorithms, researchers strived for a total automation. In the last few years, however, the focus has shifted to a more realistic scenario of decision support systems. Decision support systems use genetic algorithms and neural nets to help managers in decision making. Due to the massive explosion in the size and diversity of firms, modern techniques like decision support systems are increasingly becoming necessities for large firms.
We now wish to consider scheduling from the perspective of Simon's bounded rationality. Because in general scheduling is an NP hard problem, managers aided with computers can not obtain exact optimal solutions in polynomial time. Bounded rational behavior is the use of approximate algorithms. Innovations occur in bounded rational behavior with the development of better man aided by computer algorithms that lead to better performance, and in some cases optimal performance. We wish to demonstrate this with an examination of progress in creating better algorithms for the job-shop scheduling problem.
In general, the work in a job-shop is made-to-order rather than made-to-stock and thus has crucial customer delivery dates associated with it. The main challenge of scheduling job-shops is to minimize the lateness of the jobs and maximize the throughput, both of which can be measured in different ways. Job-shops minimize inventory while attempting to meet the due dates within the known capacity constraints. Job-shop scheduling is the paradigm of choice for companies with customer customizable products.
This problems directly maps to the classic parallel programming problem which attempts to schedule a certain number of jobs of varying lengths on a given processors in a given time span. This problem is formalized as below.
Statement of the problem:
Number m Î Z+ of processors, set J of jobs, each j Î J consisting of an ordered collection of tasks tk[j],1 £ k £ nj, for each such task t a length l(t) Î Z+0 and a processor p(t) Î 1,2, ,m, where p(tk[j]) &Mac185; p(tk+1[j]) for all j Î J and l £ k £ NJ, and a deadline D Î Z+.
Many real world scheduling problems are related to the job-shop scheduling problem. Most of the scheduling techniques developed in the last forty years have been used, with varying results, for solving this problem. Tracing the history of job-shop scheduling problem would thus give us a general idea of the improvements in scheduling in the last four decades.
The origins of significant interest in the job shop scheduling problem can be traced to the two well known benchmark problems consisting of 10 jobs and 10 machines as well as 20 jobs and 5 machines. Both of these problems were introduced by Fisher and Thompson (1963). While the case of 20 jobs and 5 machines was solved in 10 years, the instance of 10 machines and 10 jobs took 25 years of extensive research to solve. Better solutions of the later case are still being explored. Lageweg in 1984 found an optimal schedule of 10 by 10 problem that Carlier and Pinson (1989) proved to be optimal. They used the branch and bound method to solve the problem. Since then several other branch and bound algorithms have been applied to find better solutions to the problem. Carlier and Pinson (1991) showed that the problem can be solved to optimality within less than 2 minutes of CPU-time on a small work station.
As approximation methods became popular in the early 90s, researchers applied them to solve the 10 x 10 job shop problem. The efforts to apply simulated annealing, tabu search, parallel tabu search and genetic algorithms culminated in the excellent tabu search implementation of Nowicki and Smutnicki (1993) and Balas and Vazacopoulos (1995). They achieved greater efficiency.
The job shop scheduling problem remains one of the most difficult combinatorial problems to date and arouses new research interest. The exact solution methods perform well only for some specific instances of the problem of the same size. They usually perform poorly for the instances of different size. Heuristics such as simulated annealing, tabu search and genetic algorithms are generally more robust under different problem structures and require only a reasonable amount of implementation work with relatively little insight into the combinatorial structure of the problem. Instances of the problem larger than 10 x 10 proposed among others by Adams, Balas and Zawack (1988) still remain open. There is thus continued interest in the problem as more efficient and robust solutions are being explored.
The approximation algorithms have not only facilitated the adoption of new manufacturing paradigms for firms, but have acted as major catalysts in the conception and implementation of new paradigms. Advances in the approximate scheduling methods have facilitated the gradual implementation of production of final demand.
Today markets are turbulent and dynamic. Tremendous advance in the field of information technology, microprocessor technology and artificial intelligence(application to scheduling and decision support) in the last decade or so have turned the vision of agile manufacturing into reality. It is increasingly becoming possible for the firms to achieve short product development cycle times and respond immediately to sudden market opportunities (Agility Forum, 1994). With time we are achieving better solutions but we are still far from the optimal. It has taken more than 40 years and billions of dollars in research and development for firms to reach this stage and there is still a long way to go. The scheduling algorithms are still far from being optimal in the general case.
Much innovation is creating better approximations to difficult problems. We use scheduling because the problem is clearly defined, but we strongly assert this applies to a large number of problems, which may not be clearly defined, that firms face.
3. Balas, E., 1969, Machine Sequencing via Disjunctive Graphs: An
Implicit Enumeration Algorithm, Operations Research,.17 (6), pp
941-957
4. Balas, E. and Vazacopoulos, A., 1995, Guided local search with
shifting bottle neck for job shop scheduling, Management Science
Research Report \#MSR R-609, Carnegie-Mellon University, Pittsburgh
5. Barker, J. and McMahon, G., 1985, Scheduling the General Job Shop, Management
Science, 31 (5) pp 594-598
6. Bellman, R., Esogbue, A. and Nabeshima, I., 1982, Mathematical
Aspects of Scheduling and Computations, (Pergamon Press: Oxford)
7. Blazewic, J., Ecker K., Pesch E., Schmidt G. and Weglarz J., 1996, Scheduling
Computer and Manufacturing Processes (Spring: Berlin)
8. Carlier, J. and Pinson, E, 1994, Adjusting heads and tails fro
the job-shop problem, European Journal of Operations Research,
78, pp 146-161
9. Cerny, V., 1985, Thermodynamical approach to the traveling salesman
problem: an efficient simulation algorithm, J. Optimization Theory
and Applications, 45, pp 41-51
10. Cook, S., 1971, The Complexity of Theorem Proving Procedures, Proceedings of the 3rd ACM Symposium on Theory of Computing, pp 151-158
11. Dorn, J. and Froeschl, K (ed), 1993, Scheduling of Production Processes (Ellis Horwood: New York)
12. Edmonds, J., 1965, Paths, Trees, and Flowers, Canadian
Journal on Mathematics, 17, pp 449-467
13. Fisher, H., and Thompson, G., 1963, Probalistic learning
combinations of local job-shop scheduling rules, in Muth, J., Thompson,
G. (eds), Industrial Scheduling (Prentice Hall: Englewood
Cliffs, NJ)
14. Gomory, R., 1958, Outline of an Algorithm for Integer Solutions to
Linear-Programs, Bullitin of the American Mathematical Society,
64,pp 275-278
15. Karp, R., 1972, Reducibility among Combinatorial Problems, in
Miller, R. and Thatcher, J. (eds) Complexity of Computer Computation
(Plenum Press: New York), pp 85-104
16. Kirkpatrick, S., Gelatt, C. and Vecchi, M., 1983, Optimization by
Simulated Annealing, Science, NO. 220, pp 671-680
17. Land, A. and Doig, A., 1969, An Automatic Method of Solving
Discrete Programming Problems, Econometrica, 28 (3), pp 297-520
18. Little, J. et al., 1963, An Algorithm for the Traveling Salesman
Problem, Operations Research 8 (2), pp 972-989
19. Lewis, R., and Papadimitriou, C., 1998, Elements of the Theory
of Computation, Second Edition, (Prentice-Hall: Upper Saddle River,
NJ)
20. Nowicki, E. and Smutnicki C.,1993, A fast taboo search algorithm
for the job shop problem, Management Science
21. Rechenberg, I., 1973, Optimierung technischer Systeme nach
Prinzipien der biologishchen Evolution (Problemata:
Frommann-Holzboog)
