The Kenshu: Japan's Corporate Initiation Rite.
Widespread misconceptions about life in large Japanese corporations led Mei to
set the record straight on the
kenshu, the four-month mandatory training session for new
employees.
Hooked on Computer Graphics. Co-authored
with Sakae Uno. The
Japanese fascination with electronic gadgets, combined with the
national interest in mathematics and
computation, has given rise to impressive work in computer
graphics.
Reflections of a Japanese Repatriate.
Insights on living and working in
Japan by the author, who grew up in the U.S. and now works in
Japan.
The Traveling Salesman Problem: PCBs, Punch
Presses . . . and
Pachinko. Co-authored with Shinji Misono and Kazuo. The wildly
popular pinball game called
pachinko gives Japan a novel manufacturing application of the
TSP.
Listening for Defects: Wavelet-Based Acoustical Signal Processing in Japan. A report on some promising industrial and medical applications of the wavelet transform method in Japan.
The Kenshu: Japan’s Corporate Initiation Rite
Sneeze! . . . sniffle, sniffle, as I wipe the tears from my eyes.
Yes. It is the sugi pollen season. And soon to follow are the sakura viewing festivals. For permanent employees of large corporations in Japan, early April is a time that brings back memories of their initiation ceremony, or nyu-sha-shiki, and the four-month mandatory training session known as the kenshu that immediately follows it. Both are vehicles used to ease recent college graduates, who begin work on the uniform Japanese corporate hiring date of April 1, into a new environment and the corporate culture.
Each firm designs its own program to meet its specific needs, but there is a large degree of similarity among firms catering to the same customers. I work for a computer company, so my kenshu program was probably similar to those of my counterparts at other large electronics firms.
By recounting my kenshu experiences in this article, I hope to give readers a glimpse of one of the rituals associated with Japanese industrial life. I decided to put my recollections into print after many a cocktail party conversation and café chat indicated to me that numerous (mostly negative) misconceptions about the process were floating around the English-speaking community, both here in Japan and abroad. Although a main purpose of the kenshu is to instill a spirit of corporate loyalty, it was not an unpleasant experience filled with indoctrination, voodoo, or whips and chains. It was actually somewhat like summer camp, except that we got paid.
The conditioning of new employees begins on day one, at the opening ceremonies. We are all welcomed to the club, so to speak. A full day is spent listening to long talks meant to inspire young, anxiety-ridden workers. Everyone is dressed in a new suit, trying desperately to look professional and hoping for a magic transformation. The scene is reminiscent of the opening exercises of freshman week at college.
Several aspects stand out vividly in my memory. The coffee breaks reek of cigarette smoke, which nonsmokers must grin and bear. (A large percentage of the Japanese population smokes, and, unlike in the U.S., smoking is not publicly discouraged.) The Japanese audience is quiet, passive, and mild mannered. Any boredom or rebellion is expressed through daydreaming and rather overt midlecture sleeping and snoring.
At the end of the long day, I pick up my initiation packet and make my way into the crowded train station. The packet tells me that the first several weeks will be spent in a general course, or godo kenshu. Phase two will be a specialized course for engineers, the gijutsu kenshu. The program will end with an internship, the genba jisshu.
(The recent recession in Japan has led many companies to reduce their kenshu programs, but six years ago, when I entered the workforce as a basic research engineer, most electronics firms followed this three-step kenshu format for their engineers. Only the third course differed, depending on the engineer’s final destination: Basic research engineers normally interned in a product development lab, whereas development and manufacturing engineers interned in a sales support department or a factory, and manufacturing engineers worked on the assembly line. By interning one step closer to a product or customer, the new employees could gain some perspective on how their work fit into that of the entire company.)
The godo kenshu is by far the most fun, at least for the engineers. We are the only ones who know our first work location and assignment before the kenshu. It is much more serious business for nonengineers, whose jobs are assigned on the basis of their performance in this first course, which deals mainly with business etiquette, workday and business-trip schedules, corporate history, and the goals, product lines, and services of the firm. Good citizenship, personal health, and physical education are also covered. In very old-fashioned professions, like banking, the godo kenshu may even play a significant role in determining an employee’s career track.
Nonscientists with good interpersonal skills and special talents (semipro karaoke singing, standup comedy) will be placed in customer relations and sales. In these areas, it is important to be able to figure out—taking into account relationship, relative rank, and age difference—precisely how deeply to bow when meeting or bidding farewell to another businessperson. Although engineers may venture to invent high-tech training devices like the giant protractor used to measure the angle of someone’s bow, we can safely leave bowing practice to the budding sales and customer relations representatives.
Every few days, the classroom location is moved to a different hotel. According to folklore, the purpose of this constant shifting is to train non-Edokko* in the use of maps, timetables, and train route maps so that they can calculate travel times within the greater Tokyo metropolitan area. During the first few weeks, the punishment for tardiness is mild: Offenders have to sing a nursery song (“po po po po, hato po po po”) in front of the class. As the course progresses, penalties can become more serious and involve cuts in pay or vacation time.
For the engineers, there is not much substantive material in this kenshu—a handful of lectures on the history of the company and its product lines, tips on social etiquette (e.g., how to answer phones, exchange meishi,* or seat people properly at a dinner table or in a taxicab), and a one-day crash course on what to do when meeting a foreign businessperson.
We view miles of videotape produced by the R— Corporation. In almost every large Japanese corporation, the faceless and bland business style is taught by means of these tapes, plus a multiple-choice quiz. After class, we all laugh at the questions: How many buttons can a proper salaryman* have unbuttoned on his vest? on his jacket? when sitting? walking? standing? giving a presentation?
A few days of enduring this comedy of sorts produces many lifelong friendships. Aha! We have hit the nail on the head. The main point of this course, for engineers, is to establish good informal relationships with people who will work in many different branches and subsidiaries of the company.
The highlight and finale is a one- to two-week trip to a mountain lodge. The Japanese efficiently pile in and out of the buses and follow a guide who waves a little colored flag; they grew up in a culture in which overnight school field trips tutored them in the logistics and mechanics necessary for successful group travel.
I am the only PhD who doesn’t fall ill after spending a week in a dormitory-like environment with 22- to 24-year-olds. One is even hospitalized. Most of the Japanese lived at home while attending college and had little experience of dorm life or independent living. The trip gives them an opportunity to spread their wings; it also allows instructors to observe who is inclined toward a responsible lifestyle. There is much fun and laughter, but after several days of compulsory morning exercises, institutional cuisine, and sleepless nights, we are all relieved when we can make our tearful farewells and go home.
The gijutsu kenshu is quite a contrast to its predecessor. The atmosphere, for instance, is quiet and subdued. In the godo kenshu, there were parties or dinners almost every evening, usually in flashy sections of the city, and even bigger bashes on Fridays; in the gijutsu kenshu, the engineers tend to organize outings only for Friday nights, and to more sedate places like cheap Chinese restaurants or yakitori grills. Perhaps engineers tend to be introverted.
Here we supposedly learn the assembler computer language and the basics of computer hardware and software. (I am still trying desperately to learn Japanese.) All work is done in groups, and the importance of teamwork is emphasized. Field trips consist of visits to factories, clean rooms, and labs. Some companies, it is said, even train their engineers to write patents at this early stage. Yes, this kenshu is definitely more serious business for engineers. The friends we make in this course are similar to study pals from college. At the end of six weeks, farewells are mostly polite bows, the equivalent of a good handshake.
Phase three, the genba jisshu, is surprisingly pleasant, with no more lectures, homework, or quizzes. We are each given a small assignment that, when completed, will contribute to a large project. I am assigned as an intern to a development group, where the atmosphere is noisy and busy compared to that of the basic research lab where I will eventually work. To facilitate communication, we sit at long tables, not in private carrels.
Although the newly hired research engineers were purposely placed in separate classes in the preceding months, we came to know each other during coffee breaks and lunch, and we all heave a great sigh on the final day of this last kenshu after we each give a 30-minute presentation on our internship. The shared misery (kuro) will bind us for the remainder of our years together at work.
In the years that have passed since my nyu-sha-shiki and kenshu, the lingering recession in Japan has forced large companies to curtail their training programs substantially. The cost of these programs in tuition, materials, lodging, and lost work time is tremendous, while the payback is difficult to measure. We can only guess as to whether the four-month, three-phase kenshu will make a comeback when the economy rebounds.
For recent new employees, it is difficult to predict the long-term effects of being spared this not-so-grueling initiation rite. At the very least, they will have lost out on a personal level by not having had the opportunity to make friends outside their own offices and to share memories of a party or a kampai! under the cherry blossoms with co-workers from the same entering class.
Mei Kobayashi is a researcher in the Media Systems Institute at IBM Tokyo Research Laboratory.
Reprinted from SIAM News
Volume 27, Number 7, August/September 1994
Copyright 1994 by the Society for Industrial and Applied Mathematics
All rights reserved
In Japan, amateurs as well as professionals are tuning into CG wizardry and the mathematics behind it.
Perhaps even more than by the Western culture that created her, Mona Lisa and many other great classical, Renaissance, and impressionist works are adored by the Japanese public. Advertising firms and computer graphics (CG) scientists have added high-tech twists to many of these popular works to promote various products and newly developed technologies. The Mona Lisa who ate too much turns to a low-calorie sweetener and reverts to her original graceful form via morphing. At the University of Tokyo’s Harashima Laboratory, the lovely Mona Lisa can talk, thanks to a three-dimensional model of a human face in motion plus a two-dimensional photograph-to-model map.
These examples of CG wizardry, ubiquitous on television and in video games, derive their appeal not only from the “Europa boom” in Japan and the love of electronic gadgetry among the younger Japanese, but also from the Japanese fascination with the mathematical and computational sciences. In this pro-intellectual society with a tradition of respect for learning and teachers, many people study or play with mathematics as a hobby even after their formal schooling ends. Popular mathematics magazines are available in various degrees of difficulty, and they often contain articles by distinguished professors. Now, new developments that make it possible for amateur scientists to create their own graphics programs have provided further inspiration for mathematical studies in Japan.
For amateurs and professionals alike, computer graphics is indeed an exciting and important area of research. Work in this area can be classified into two categories: first, the use of CG to generate photorealistic images, such as computer renditions of potential buildings or destroyed castles, which help us “imagine the real”; and second, the use of CG as a tool for displaying results from complex modeling and simulation experiments, which allow us to “realize the imaginary.” Examples of CG work in the second category, in addition to Mona Lisa in her infinite variety, are large-scale computations that require millions of data sets and produce huge volumes of output. This output is difficult to understand and interpret without an organized visual presentation or “visualization.”
Both photorealistic image generation and visualization require sophisticated mathematical analysis and algorithms, creating new frontiers of research that have led to increased interaction among scientists from different disciplines and nations.
Graphics work in the first category uses a variety of mathematical tools. In the computer modeling of buildings for architectural purposes, for example, solid modelers from a menu of 3-D geometric building blocks (such as bricks, cylinders, and spheres) are used to create the main structure. These solid modelers help architects to fit together pieces of the correct size and proportion and to try out small variations in design without having to construct real miniature 3-D models. Colors and textures are applied to the surfaces, and texture mapping and shading are added to create a 3-D-like atmosphere. Mathematical tools used for texture generation include fractals and random numbers. The specialized mathematical models and high-speed algorithms used for shading and shadowing calculations constitute an active area of research.
To woo potential customers, large Japanese architectural construction firms hire applied mathematicians and computer scientists to produce videos of simulated walk-throughs of proposed buildings and mall complexes. An impressive tape produced by the CG team at Taisei Corporation, one of these giant firms, consists of breathtakingly beautiful computer renditions of historical sites. “Ancient Civilizations” takes the viewer on a time-travel trek through Mesopotamia, the Nile Delta, ancient Greece, the Mongolian empire, and Aztec cities as they might have looked to those who lived there.
A large portion of CG work in the second category uses simulation techniques. In Japan, this work is primarily driven by industry needs. For example, mathematical modeling has been used for quite some time in the design of automobiles, robots, assembly lines, and electronic devices. More recently, high-tech firms have routinely used results from simulations of clean rooms and their air circulation systems to improve facilities. Movement studies of human-and/or robot-induced contaminants use complex adaptive meshing schemes and computational fluid dynamics models. With no clear-cut, easily implementable, and aesthetically pleasing method for generating a mesh and simulating airflow, a great deal of fine-tuning by experienced numerical analysts is needed to extract meaningful results. Articles on this topic regularly appear in the journals of academic societies and major electronics firms.
The classification of CG work into two categories is somewhat artificial, and techniques from both are often used to complete a task. In the future, new CG technologies, improved algorithms, and more powerful computers will undoubtedly allow scientists to create hybrid technologies and disciplines, as currently epitomized by virtual reality (VR). Possible applications of VR include affordable walk-through simulation systems, virtual surgery (for training of medical students), and more realistic video and entertainment games. A sneak preview of future VR systems and their powerful commercial potential can be seen at the Matsushita showroom in Tokyo, where potential customers can experience a VR stroll through a variety of model kitchens.
Of course, CG scientists have less flashy media than television, video parlors, or data shows to display their wares. Scientists who wish to become acquainted with current computer graphics work in Japan might consider submitting a paper for the NICOGRAPH conference held in Tokyo every November. The NICOGRAPH (Nippon Computer Graphics) Association is a nonprofit industrial organization for the promotion and investigation of CG and computer-aided design. The week-long conference, which consists of exhibitions, seminars, tutorials, film shows, and a paper competition, is regarded as the largest and most important CG event in Japan.
The NICOGRAPH paper competition has actually become something of an omatsuri, or festival. Of course, it does not literally have taiko drummers and dancers, but it is a happy and uplifting occasion, especially for the young. In fact, many teachers feel that the competition is invaluable for inspiring their students. A new category of paper, the case study, was established in 1993 to encourage young industrial engineers to submit papers summarizing results of their work, which often differs in character and emphasis from academic CG studies. In recent years, submissions by non-Japanese scientists have increased substantially, giving the meeting a more international flavor.
Scientists who intend to spend a year or more in Japan might consider joining one of the larger academic societies, such as the Joho Shori Gakkai, the Information Processing Society of Japan (IPSJ), or the Denshi Joho Tsushin Gakkai, the Institute for Electronics, Information, and Communication Engineers (IEICE). Both societies hold large semiannual meetings that give attendees a good overview of trends in the theory and applications of information technology. Both also have smaller special interest groups with quarterly or monthly meetings.
IPSJ’s Special Interest Group on Computer Graphics and Computer Aided Design (SIGCG) has a tradition of holding a two-day summer kenkyukai (technical conference) at a small ryokan (inn) near Hamamatsu, a lakeside town about 160 miles west of Tokyo. On the evening of the first day of the conference, there is always an enkai (banquet) followed by a konshinkai, an informal get-together where drinks flow freely. The rationale is that “nomunication” (a Japanese jargon term combining “nomu,” to drink, and “communication”) relaxes everyone, and special friendships develop through the ensuing informal technical discussions. Scientists and engineers tend to be shy and introverted, so these parties are unusual and treasured opportunities to get personally and professionally acquainted with others.
Recent summer kenkyukai have focused on the themes of visual art and design (1992); sensibility, arts, and multimedia (1993); and CG and sensibility (1994). The speakers and participants include a healthy, exciting mix of engineers, computer scientists, and artists, all of whom use CG in various contexts.
Japanese graphics gurus as well as buffs eagerly await the special issue of the IPSJ SIGCG Notes that contains its annual survey of CG publications. The survey, which is also available on a floppy disk, covers international and domestic academic journals, commercial magazines, and technical reports from selected enterprises. About 50 books and 1000 papers and reports are reviewed and classified into 12 categories and indexed by keywords.
Many young Japanese scientists also aspire to present their work at the annual meeting of the Association for Computing Machinery’s Special Interest Group on Computer Graphics (ACM SIG-GRAPH), regarded as the most important and prestigious conference on computer graphics in the world.
If Japan can continue to promote computer graphics and mathematics as fun sports as well as serious science, who knows? Perhaps within this century we will meet up with a Mona Lisa who can dance with us in a virtual world. In any case, SIAM News readers may agree that the greatest Mona Lisa of all was the first, for she has inspired so many to study mathematics! (wink)
Mei Kobayashi (mei@trlvm.vnet.ibm. com) is a researcher in the Media Systems Institute at IBM Tokyo Research Laboratory. Sakae Uno (uno@trlvm.vnet.ibm.com) is program manager for research quality at IBM Tokyo Research Laboratory and a former manager of the TRL graphics group.
Reprinted from SIAM News
Volume 27, Number 8, October 1994
Copyright 1994 by the Society for Industrial and Applied Mathematics
All rights reserved
Reflections of a Japanese Repatriate
Tadaima! (I’m home!), I cried out. I could hear the pitter-patter of my grandmother’s feet as she came from the back to greet me. My grandmother had taken me under her wing, helping me to adjust to my new life in Japan and my job at IBM Tokyo. I was living in a sunny eight-tatami* room above the drugstore she owned.
Although I had been born in Tokyo, I was raised in North America and had never expected to return to live in Japan. But in 1988, my final year of graduate school, employment prospects for mathematicians were poor, and I decided to explore some unusual opportunities, including jobs abroad. In the early fall, I sent off a handful of letters to various large Japanese corporations. Replies were prompt and courteous, and within a few months I had interviews and job offers. In mid-March, not wanting to risk ending up on the U.S. unemployment roster in September, I frantically packed my worldly belongings into 15 cardboard boxes and left for Tokyo. I am now a happy and settled repatriate, but the transition was not without its rocky moments.
When I arrived in Japan, I went through the culture shock associated with the high cost of living much publicized by the Western press ($3 for a cup of coffee, $4 for an orange). But I quickly figured out how people manage to live quite well. Monthly take-home salaries are surprisingly large, while tax rates are relatively low, and most large employers provide an allowance for commuting and housing. I soon discovered the many discount and secondhand stores in the side streets. Many “recycled” items in the so-called recykuru shoppu are actually brand-new, the would-be waste products of a society with a gift-giving tradition based on obligation rather than friendship.
Commuting was a second culture shock. Every morning I ran to the station and piled into one of the historic green cars of the Setagaya trolley, which rattled and shook under its overload of passengers, and then into a sleek silver car of the Shintamagawa subway line. Professional railway pushers with bleached white gloves “helped.” Climbing in, forcefully, against a solid wall of passengers is difficult, but popping out in one piece, uninjured, is an art.
Even though Japanese public transportation is convenient, clean, and reliable, commuting was an exhausting daily exercise. I am not alone in thinking so. A recent poll revealed that urban Japanese find the workday commute to be the most unpleasant aspect of their lives.
A minor but noteworthy adjustment for me was getting used to having more than one Kobayashi in most business and social meetings. During the ceremony for new employees on my first day of work, I sat next to a Mr. Kobayashi. I had four neighbors named Kobayashi. I currently belong to a research group with three, and two of us share the same initials; despite eerie Orwellian overtones, we have taken to addressing each other via userid names (“MKOBA-san,” “KOBAK-san,” or “KOB9-san”). On the other hand, even though we are not related, it is easy to make friends with and feel an immediate kinship with other Kobayashis.
Not all cultural adjustments have been uphill battles. The near-absence of crime and freedom from annoyances like erroneous billings and undependable deliveries of items are wonderful aspects of Japanese city life. In small as well as in large dealings, businesses honor their word; the customer is king.
As a customer, I find Japanese reliability reassuring, but as a salaried worker, I have discovered that the high quality of goods and services also means that I am pressured to keep to a precise schedule. My job in a basic research laboratory has offered me some insights as to how the Japanese workplace functions so smoothly. Efficient and coordinated teamwork is encouraged and nurtured. Because the payscale is based on seniority rather than merit, there is little competitiveness within the workplace, and colleagues pitch in during crises. It helps that Japanese society is fairly homogeneous in daily customs and in income level; the slight regional differences make interactions interesting but do not cause schisms.
Homogeneity also helps workers maintain a peaceful co-existence with associates in crowded offices, many of which lack even carrels or booths. At first I found the lack of privacy disturbing, but the concept of individual and territorial rights began to fade in time. Camaraderie and a warm, family-like atmosphere develop quickly among neighbors at work.
It is common for managers to express parental-like feelings of warmth and concern for subordinates and to send personnel to help with family emergencies and company-ordered moves. Some traditional Japanese firms, such as banks, even have an informal policy of helping out (or meddling) with the personal lives of employees. Matchmaking-inclined elders sometimes scout out prospects for eligible singles in their department, creating crafty scenarios for those averse to the idea of the traditional omiyai with a go-between.
In the past, because statistics indicated that almost all significant scientific work (including that leading to patents) was produced by workers during their 20s and 30s, scientists in many Japanese basic research labs could expect to be assigned to another area of the company, such as technical sales support or product planning and development, once they reached the age of 40.
But during the economic boom a few years ago, large corporations accelerated their hiring and were faced with a shortage of experienced managers and keepers of wisdom. In Japan, it is difficult to hire such people from outside and successfully integrate them into a corporate setting; feelings of resentment inevitably arise among the already established. So most basic research labs decided to allow talented scientists to remain after the age of 40, to contribute academic expertise and mentors for the young. It seemed as if they had heeded the moral of the Japanese folktale “Uba Sute Yama”*.
Unfortunately, the recent economic slowdown seems to have put this policy on hold. Corporate research scientists fearful of losing their scientific freedom are fleeing to universities and government research institutes. For those who are lucky or brave enough to stay in corporate labs, the economic downturn has also brought a revival of policies encouraging market- and product-driven work at the expense of basic scientific research.
In Japan, most white-collar workers can and do expect financial comfort and job security, even for a lifetime of unexceptional performance. A worker is motivated by personal pride and the desire to be an accepted member of a workplace team and of society; the ultimate “loss-of-face” is to be banished forever from the central workplace to a corner seat and labeled the office mado giwa zoku—literally, one who sits next to a window (and spends idle hours peering at passersby). But the expectation of lifetime security is turning out to be something of a mirage. The recent recession has forced companies to pare down their overloaded workforces and aggressively solicit “voluntary” early retirements.
One of the happier byproducts of the recession is a reduction in overtime work. Even before the slump, I was fortunate in having kind managers who valued personal life as much as work and believed in the importance of refresher breaks and vacations. Unlike that of my parents and my managers’ parents, our generation has not experienced the ravages of war and the ensuing austere life. Perhaps seeing and experiencing different cultures through leisure as well as business travel will place those of us who had a gentler childhood in a better position to lead Japan into a successful and peaceful future, with a greater sense of world statesmanship.
I eventually moved out of my grandmother’s house to a one-room apartment, close enough to visit her, but far enough away to allow her to retain her spirit of independence. My grandmother died last year after an extended illness. Although she was denied the opportunity of a formal education because of both the era she lived in and her gender, she had become a successful career woman in her own right, establishing and managing her own store. Her straightforward, no-nonsense talk, honesty, and diligence had made her a role model in our family. In my move here, I was blessed not only with the warmth and comfort of her home, but also with the wisdom of her years and her faith that I could make the difficult transition. And so I dedicate this article to Yoshie Kobayashi, 1908–1993.
Mei Kobayashi (mei@trlvm.vnet.ibm. com) is a researcher in the Media Systems Institute at IBM Tokyo Research Laboratory.
Uba Sute Yama. Once upon a time in a little village, citizens whose mothers had reached a certain age were required to carry them to a remote mountain top and abandon them. One fellow, who could not bear to part with his mother on the summit, secretly took her back home. Soon afterward, a feudal lord passed through the village and asked many questions. The only one who could answer the questions was the old mother in hiding. She coached her son, and he impressed the lord with his answers. When the son revealed that the wisdom was his mother’s, the lord and townspeople agreed to revoke their uba sute yama policy and to recognize the wisdom and valuable contributions of the elderly to society.
Reprinted from SIAM News
Volume 27, Number 9 August/September 1994
Copyright 1994 by the Society for Industrial and Applied Mathematics
All rights reserved
The Traveling Salesman Problem: PCBs, Punch Presses . . . and Pachinko
Over the clinking of little silver beads, a gunkan maachi (military march) melody trumpets on as customers of different ages and genders sit alert, perched on plastic stools in front of pachinko (Japanese pinball) machines. Staring at vertical boards studded with hundreds of nails, the pachinko players (who number nearly 30 million in Japan) watch as the beads dance around the nails and either sink into jackpot holes as "hits" or wiggle their way down to the bottom booby tray. At 100 yen (about $1) per set, pachinko is a low-risk form of gambling, even for addicted players, but the annual 20 trillion yen ($200 billion) pachinko market clearly represents high stakes for the industry.
As pachinko has evolved, a player’s success, once dependent on at least some manual skill, has come to depend only on the alignment of the nails on the board. When pachinko was first introduced-in Nagoya, Japan, shortly after World War II-serious players loaded handfuls of beads into the machine with one hand while aiming and shooting the beads, using a spring-powered bar or lever, with the other. Wins and losses were based on players’ skill in the initial aim and on careful control of the initial impulse, as well as on the alignment of the nails.
Several years later, automatic loading machines were introduced, allowing players to focus completely on shooting and aiming the beads. For the past decade and a half, all boards have come equipped with an automatic shooting device that relieves players of any obligation to be deft. Now, using a simple dial, players can control only the initial force imparted to the beads. On a rainy day in central Tokyo, a queue of umbrellas awaits the opening of each pachinko parlor. At the sound of the bell, aggressive gamblers elbow their way in, hoping to discover the day’s lucky seats. Clearly, elves have once again toiled past midnight to switch boards or realign the troublesome tilted nails that permit easy jackpots.
As players and parlor owners study nail positions and tilts, manufacturers are researching more efficient methods for producing boards. For a given alignment of nails, determining the fastest or a near optimal order for hammering in the nails is one of the most challenging variations of the traveling salesman problem (TSP) arising in industrial manufacturing. A brief discussion of a number of familiar industrial applications of the TSP will give readers an idea of the status of the pachinko board manufacturing problem among those applications.
The TSP can be stated clearly and exactly in simple terms: Given a set of cities, find the shortest route that will allow a salesman to visit each city exactly once. The apparent simplicity of the problem, coupled with its substantial difficulty as a representative example of NP-complete problems, has attracted many researchers. Considerable effort has been devoted to obtaining exact solutions of the TSP, and many heuristics for obtaining approximate solutions have been developed. The TSP has also served as a performance benchmark for heuristics (such as genetic algorithms) designed for solving hard problems. The TSP can be used to model a variety of problems that require minimizing the total operation time of a numerically controlled machine by manipulating its control data; such problems arise in computer wiring, vehicle routing, job sequencing, and X-ray crystallography.
The classic application of the TSP is the printed circuit board (PCB) drilling problem: Given a set of required holes of specified diameter, find the drilling route that minimizes the route traversal time. Each hole is regarded as a city in two-dimensional space, and the distance between two cities is defined as the machine-time distance, that is, the time needed for the drilling head to travel between these holes. A typical finished circuit board panel will have holes of three to 15 different sizes and can have as many as 65,000 holes in all. The drilling head moves horizontally to change locations and vertically to drill a hole. Only one drill bit can be mounted at a time, and bits must be changed at stations located next to the target panel. Since the time required for changing tools is more than twentyfold the time required to traverse the diagonal of a panel, holes of the same size should be drilled consecutively.
Numerous refinements of the PCB problem take into account other factors. For example, total operation time can be further reduced by taking the average life span of a drill bit into consideration when optimizing a drilling route. A second variation, the test coupon problem, models drilling systems without automatic bit-break detectors. Since all holes drilled after a bit break must be redrilled, extra holes, called test coupons, are drilled in a special panel every thousand or so holes to enable premature breaks to be easily detected.
In a third variation, the short-distance-avoidance problem, a minimum-separation-distance constraint is imposed. The method is based on the assumption that a drill bit does not have sufficient time to dissipate the heat acquired during the drilling process if the interval between two consecutive drillings is too short. If the temperature of a bit rises, its effective life span is reduced, and a large time penalty may be incurred in the form of numerous time-consuming bit-change operations. This penalty far outweighs the reduced travel time that results from drilling holes close to each other.
A case study at one Japanese PCB manufacturing plant showed that when a TSP heuristic replaced a method determined by standard engineering techniques, drilling route length was reduced by 80%, yielding a 15% reduction in the total drilling time and a cost reduction equivalent to about a million dollars annually. (There are two main reasons for the discrepancy between the two reduction values: First, horizontal motion accounts for less than 30% of the total drilling time, and second, the actual time spent in horizontal motion is a nonlinear function of the geometric distance when acceleration times are taken into account.)
In other TSP applications, more types of variables are involved and/or the time susceptible to optimization occupies a larger portion of the total operation time than in the PCB problem. Consequently, a significant reduction in total operation time can be expected by applying TSP heuristics to optimize control of machines.
An application with two types of variables is the punch press machine (PPM), which transforms steel boards into prescribed shapes by punching or pressing with various tools. The punching head consists of a striker and a tool holder with fixed locations for the tools. PPMs differ from drills in two respects: First, tools can be changed while the holder is moving horizontally, thus reducing delays due to tool change. Second, point punching is a very fast operation, so that a large portion (roughly 80%) of the total operation time of a punching machine is spent on tool changes and horizontal motion.
The total operation time of a PPM is therefore strongly influenced by optimization techniques. The solution to this type of problem requires the simultaneous optimization of the punching route and the tool-selection order. In a typical scenario, tools of five to 20 types are used, and the number of punching points for each tool varies from ten to several thousands and can run as high as 85,000. In numerical experiments, use of TSP solution techniques produced a 12% reduction in motion and tool change time (a 9% reduction in total operation time).
The control of a surface chip mounter is another optimization problem with more than two types of variables. It is mathematically the same as the punch press problem, except that the locations of the tools are variable rather than fixed. Competition among mounter manufacturers is very stiff, and mounting speed is recognized as a major factor in gaining market share.
A complicated and dynamic offshoot of the TSP is the flying probe problem: Find the set of routes that minimizes testing time for a circuit tester with multiple probes, each of which moves simultaneously and independently (i.e., determine a route for each of the probes). The tester checks for open- and short- circuit faults in a multichip module substrate by bringing two or more probes into contact with pins in the substrate. Each test is specified by a set of locations for the test pins. The optimization problem here is to determine collision-free probe routes that minimize the traversal time for a given list of tests.
An interesting offshoot of the TSP is the traveling cameraman problem: For a given layout, find the locations of check points and checking routes of a security camera that will minimize the total checking time. An approximation algorithm to solve this automatic optical inspection problem has been developed by Iwano, P. Raghavan, and H. Tamaki.
One of the most sophisticated open problems of the TSP genre is the pachinko board manufacturing problem: Find the route of a hammering head that minimizes traversal time to create a pachinko board with several hundred nails. Among the complicating factors for this problem is that the hammering head moves over the board at an altitude lower than the height of a hammered-in nail, i.e., a head cannot pass over nails already embedded in the board. The optimal machine-time distance between two nail positions is therefore defined as the shortest path between them that never passes over embedded nails. Since inter- nail distances change dynamically as the nails are hammered in, a very fast algorithm must be developed to solve this problem.
In this era of high-tech wizardry, a new twist has been added to challenge players, shopkeepers, and manufacturers: the casino-pachinko machine. As in slot machines in Las Vegas (and elsewhere), three rows of flashing, ever-changing symbols-fruits or numbers-have been introduced, center stage, into pachinko boards. If a bead rolls into a lucky slot precisely when three lucky symbols are flashing, tulip- like blossoms open around the "lucky strike" region and increase the probability of a double or triple jackpot hit.
Dedicated players now search for machines that allow easier access to these lucky slots. Manufacturers, although they have devised ways to give customers the impression of machine friendliness, seek in practice to develop fruit/number generation algorithms that favor the owners over the long run. Research on these algorithms represents an upcoming, promising opportunity for mathematicians and computer scientists.
Cheers to pachinko fans and the pachinko industry! Indeed, they’ve come a long way from post-World War II Nagoya and have inspired some good mathematics.
Mei Kobayashi (mei@trlvm.vnet.ibm.com) and Shinji Misono (misono@trlvm.vnet.ibm. com) are researchers and Kazuo Iwano (iwano@trlvm.vnet.ibm.com) is manager of the Research Operations Office at IBM Tokyo Research Laboratory. A technical report on industrial applications of the TSP is available from Misono or Iwano.
Reprinted from SIAM News
Volume 27, Number 10, December 1994
Copyright 1994 by the Society for Industrial and Applied Mathematics
All rights reserved
Listening for Defects: Wavelet-Based Acoustical Signal Processing in Japan
"Arigato gozaimasu (thank you)," said the clerk in the china store, bowing. Before wrapping the hand- painted rice bowl, she held it upside down and tapped the china with her fingernail. It chimed, beautifully. She smiled-the ceramic piece was intact, free of microscopic and internal cracks.
Over the centuries, simple sound tests like this one have been applied in a variety of contexts, from assuring the quality of handicrafts to selecting a ripe Fuji apple. More recently, sophisticated sound- reading equipment, coupled with signal-processing methods, has been used for quality control in highly automated assembly lines. Computer disk manufacturing plants, for example, spin freshly produced disks at high speed and use Fourier transforms to check the resulting sounds for irregularities.
For some time, the standard tool for acoustical signal processing has been Fourier spectral analysis. The technique has been studied extensively and is, for the most part, serviceable. Some phenomena, however, have been elusive, such as the small nonperiodic signals that don’t show up after computation of the short-term Fourier transform (STFT). During the 1980s, simple experiments indicated that wavelet analysis-time-frequency analysis of the wavelet transform of data-could be very useful for the detection of abrupt changes in nonstationary signals. Unlike STFT analysis, wavelet analysis allows arbitrarily good frequency resolution at low frequencies and arbitrarily good time resolution at high frequencies. This means, for example, that when a signal consists of two short bursts, the bursts can be separated during the analysis if sufficiently high frequencies are used. Wavelet analysis also offers the possibility of robust multiresolution representation and stable, efficient associated numerical computations, features not found in Fourier methods.
These attractive properties led Hisakazu Kikuchi and his colleagues at Niigata University and Japan Electronic Control Systems to use wavelet transforms (WTs) for analyzing detonation signals in automobile engines [4]. Detonations occur because of failures in ignition advancement control (the sequence of processes that must take place to ignite an engine) and create strong pressure waves that can even destroy an engine; their detection and analysis are important for the improvement of ignition systems. Data from acoustic vibrational analysis, the main tool that has been used to study detonation signals, contain spurious information, such as noise produced during the movement of mechanical parts. Another tool, statistical analysis, is also unsuitable because detonation signals are highly nonsta-tionary. Unlike these techniques, WTs of engine sounds during the ignition process provide useful information because they allow for real-time analysis of signals with large temporal variations in a low signal-to- noise environment.
Kikuchi developed a fast WT processor for producing scalogram-like and phase-shift displays of WT data. These displays, examples of which are shown in the middle and bottom rows of the accompanying illustration, are three-dimensional representations of speech signal spectra, with time represented on the x-axis and frequency on the y-axis. Gray scales are used to represent the third dimension, either the amplitudes (for scalograms) or the phase (for phase-shift diagrams), of the WT data. In order to prevent oversight of potentially valuable information during the initial stages of the processor’s development, WTs were calculated over many more octaves and intermediate steps than in a standard scalogram (which has six octaves, with 12 half steps in between, as in a musical score). However, no distinct features were found at lower frequencies, and experiments indicated that only ten steps between octaves were needed to identify detonations. This information was used to decrease the number of computations and improve the efficiency of the processor.
Using a Gaussian-type wavelet, the processor computes the WT for five octaves concurrently, with ten steps per octave. The WT scalogram data are computed in less than a tenth the number of operations required by standard convolution methods, and even further speedups can be achieved by using a hardware system with a VLSI layout.
Two interesting follow-up experiments were conducted with the Niigata processor. One study identified what were believed to be characteristic components of engine sounds and then synthesized the sounds from the components. The resemblance between the synthesized and real sounds impressed specialists and confirmed that key components had been successfully identified.
A second study compared WT analysis and pressure sensors for their abilities to detect detonations. The pressure sensor, which provides data on the pressure inside an engine cylinder, has been the best conventional means for detecting detonations, but its use in factories is prohibitively expensive since it must be specifically tuned for each engine, driving mode (e.g., speed and acceleration or deceleration), and set of weather conditions. This study showed a very strong correlation between data from the pressure sensor and from WT analysis. In fact, WT analysis proved to be more accurate than the pressure sensor in detecting detonations and was effective at a wider range of rotational speeds [3].
In another potential industrial application, the use of WT analysis to detect irregularities in cement mixtures is being studied by Tateki Aizawa and his colleagues at Chichibu Onoda, a large Japanese cement company. WT scalograms of sounds emitted by a barrel spinning on a cement truck can indicate the existence of some types of irregularities [1]. Further refinement of the technique is under way to make such scalograms pragmatic tools for quality control.
Short-term Fourier transform analysis imposes the assumption that signals are stationary over small temporal segments-an assumption that is inappropriate for signals of biological origin because conditions inside living organisms undergo constant change. Because they do not impose this assumption, wavelet-based techniques are proving useful for processing medical acoustical data. One application area that shows promise is the compression of human electrocardiogram (ECG) data. Compression enables large ECG data bases to be established and maintained and makes the transmission of real-time ECG signals over public phone lines possible [9].
In addition to examining and evaluating compressed and subsequently decompressed ECG data on the basis of clinical experience, engineers use a number of yardsticks to "measure" the efficiency and error of an ECG compression scheme. These yardsticks include the compression ratio (CR)-the ratio of the number of bits of original data to the number of bits of compressed data-and the percent root mean square difference (PRD)-the euclidean distance between the processed and original signals expressed as a percentage of the norm of the original signal.
Jie Chen and his colleagues at the University of Electro-Communications have proposed a WT-based ECG-processing system with an optimal bit-allocation scheme [2]. In a preliminary implementation study, a simple version of the proposed signal compressor, which uses 10-tap wavelet filters, an optimally bit-allocated uniform quantizer, and a Lempel-Ziv-Welch (LZW) entropy encoder, yielded compressed data of clinically acceptable signal quality, with CRs from 13.5:1 to 22.9:1, and a PRD error between 5.5% and 13.3%. These results are significantly better than those from conventional ECG compression systems; Chen’s system, moreover, is fast, and the implementation is simple. Further improvement in the compression ratio can be expected with more sophisticated and efficient entropy encoders.
An alternative approach to ECG data compression that uses multiscale analysis of WTs has been developed by Makoto Nakashizuka and his colleagues at Niigata University [6]. It compresses data to one-tenth of the original while retaining important diagnostic features of ECG signals that conventional transform methods fail to preserve. Nakashizuka’s method uses a multireso-lution peak detector to preserve the peaks in Q, R, and S waves, which have high amplitudes and short periods and are particularly important in the detection of cardiac abnormalities.
A third approach to WT-based ECG data compression [7] is an extension of a zero-crossing technique developed by Stephane Mallat [5]. Although the compression ratio is poor (13% for normal ECG data and 18% for abnormal data, with PRD errors of 10-15% and 10%, respectively), this approach can simultaneously detect and erase noise. It remains to be seen whether comparable or better results can be obtained by first applying a noise-reduction-specific scheme, such as the one developed by Susumu Sakakibara (Iwaki Meisei University) for processing one-dimensional mechanical vibrational data in an engineering laboratory [8], and then applying a compression scheme with a higher CR and lower PRD.
Detecting irregularities through automobile engine sounds, obtaining better compression and error ratios for ECG data, preserving diagnostic features in compressed ECG signals, and clarifying noisy data are just four examples of WT-based acoustical signal processing techniques. Many Japanese manufacturing plants already use sensory data in a variety of automated quality control mechanisms, and their use is expected to accelerate as labor costs increase. Wavelet techniques show promise in improving the efficiency and quality of production, in ways that were impossible with other transform methods. For this we can all be arigatai (thankful).
The author gratefully acknowledges the assistance of Hisakazu Kikuchi and Cormac Herley in the preparation of this article.
[1] T. Aizawa et al., Electronics Magazine (Ohmsha Ltd.), November 1995, 40-41. In Japanese.
[2] J. Chen, S. Ito, and T. Hashimoto, ECG data compression by using wavelet transform, Special Section on ECG Data Compression, S. Sato, ed., IEICE Trans. Inf. Syst., E76-D(1993), 1454-1461.
[3] H. Kikuchi, private communication, October 1995.
[4] H. Kikuchi, M. Nakashizuka, H. Watanabe, S. Watanabe, and N. Tomisawa, Fast wavelet transform and its application to detecting detonation, IEICE Trans. Fund., E-75-A(1992), 980-987.
[5] S. Mallat, Zero-crossing of a wavelet transform, IEEE Trans. Inf. Theory, 37(1991), 1019-1033.
[6] M. Nakashizuka, H. Kikuchi, H. Makino, and I. Ishii, Data compression by wavelet zero-crossing
representation-application to ECG data, Tech. Rep. of IEICE, CAS93-63 (1993-09), 57-64. In
Japanese.
[7] M. Nakashizuka, H. Kikuchi, H. Makino, and I. Ishii, ECG data compression by multiscale peak
analysis, Proc. ICASSP 1995, Vol. 2, IEEE Press, Piscataway, NJ, 1995, 1105-1108.
[8] S. Sakakibara, A practice of data smoothing by B-spline wavelets, in Wavelets: Theory, Algorithms, and Applications, C. Chui L. Montefusco, and L. Puccio, eds. Academic Press, Tokyo, 1994, 179-196.
[9] Special Section on ECG data compression, S. Sato, ed., IEICE Trans. Inf. Syst. E76-D(1993), 1379-1478.
Mei Kobayashi (mei@trlvm.vnet. ibm.com) is a researcher at IBM Tokyo Research Laboratory. Beginning in April, she will also be a visiting professor in the Department of Mathematical Sciences at the University of Tokyo as part of a new program in which industrial scientists serve as teachers and thesis advisers.
Reprinted from SIAM News
Volume 29, Number 2, March 1996
Copyright 1996 by the Society for Industrial and Applied Mathematics
All rights reserved
Return to List of Articles
Return to Mei Kobayashi's Profile and Forum