Tag Archives: iphone

Did You See Any OR During Apple’s iPhone 5 Announcement? I did!

On September 12, Apple finally announced its much-awaited iPhone 5. I didn’t have time to watch the keynote speech, but I watched the shorter 7-minute video that’s posted on Apple’s web site featuring Jony Ive, Apple’s Senior Vice President, Design. In that video, at around the 5-minute, 26-second mark, something they said caught my attention: the way they put parts together during the assembly process. I encourage you to watch that part of the video before reading on.

Jony Ive says:

Never before, have we built a product with this extraordinary level of fit and finish. We’ve developed manufacturing processes that are our most complex and ambitious.

And on Apple’s web site, they say this:

During manufacturing, each iPhone 5 aluminum housing is photographed by two high-powered 29MP cameras. A machine then examines the images and compares them against 725 unique inlays to find the most precise match for every single iPhone.

So let’s see if I understood this correctly. In a typical manufacturing operation, the multiple parts that get put together to create a product are put together without much fuss. A machine makes part A, another machine makes part B, and perhaps a robotic arm or a third machine takes any one of the many part A’s that are coming down a conveyor belt and attaches it to any one of the many part B’s that are coming down another conveyor belt. What Apple did was to improve on the “any one” choice. I don’t know if Apple pioneered this idea, I’d say probably not, but this is the first time I hear about something like this. If you’ve seen this before, let me know in the comments.

Before OR comes into play, Computer Science does its job in the form of computer vision / image processing algorithms. The photographs of the parts are analyzed and (I’m guessing) a fitness score is calculated for every possible matching pair of parts A (the housing) and B (the inlay). What happens next? How do they pick the winning match? Here are some possibilities:

  1. Each part A is matched with the part B, among the 725 candidates, that produces the best matching score.
  2. A 725 by 725 matrix of fitness scores is created between 725 parts of type A and 725 parts of type B, and the best 725 matches are chosen so as to maximize the overall fitness score (i.e. the sum of the fitness scores of all the chosen matches).
  3. Proceed as in the previous case, but pick the 725 matches that maximize the minimum fitness score. That is, we worry about the worst case and don’t let the worst match be too bad when compared to the best match.

After these 725 pairs are put together, new sets of parts A and B come down the conveyor belt and the matching process is repeated. Possibility number 1 is the fastest (e.g. do a binary search, or build a priority queue), but not necessarily the best because every now and then a bad match will have to be made. Possibilities 2 (an assignment problem) and 3 (assignment problem with a max-min objective) are better, in my opinion, with the third one being my favorite. They are, however, more time consuming than possibility 1. Jony Ive says the choice is made “instantaneously”, which doesn’t preclude something fancier than possibility 1 from being used given the assignment problems are pretty small.

The result? In the words of Jony Ive:

The variances from product to product, we now measure in microns.

It is well-known that OR plays a very important role in manufacturing (facility layout, machine/job scheduling, etc.) but it’s not every day that people stop to think about what happens in a manufacturing plant. This highly-popular announcement being watched by so many people around the world painted a very clear picture of the kinds of problems high-tech manufacturing facilities face. I think it’s a great example of what OR can do, and how relevant it is to our companies and our lives.

Leave a comment

Filed under Applications, iPhone, Motivation, Promoting OR

Installing iPhone Apps: Apple Doesn’t Care About Average Completion Time

Having recently spent some time outside the US, I found, upon my return, that many of the Apps on my iPhone needed to be updated. No big deal: I clicked “Update all”, typed in my password, and let the operating system finish the job. After watching the update process for a minute or so, I noticed one interesting fact: Apps were updated (i.e. downloaded+installed) in the order the updates became available (chronologically increasing), rather than by increasing order of the size of the update (in bytes). If you’re asking “why does it matter?”, read on.

During my grad school years at Carnegie Mellon, I had the pleasure of taking the Sequencing and Scheduling class with Egon Balas (I later sat in the class again as his TA, and finally taught it to the MBA students in 2004). So let’s start with some terminology: given a machine (the iPhone) and a set of tasks (Apps) to be executed (updated) on the machine, the completion time of a task is the time at which it is finished. For example, let’s assume the Concorde TSP App needs an update. If time zero is the moment I enter my iTunes password, the completion time of task “Concorde TSP” is the earliest time at which this App’s latest version is ready to run on my iPhone. The total completion time of a set of tasks is simply the sum of the completion times of all tasks, and the makespan is the completion time of the task that gets updated last.

The App update process has no release dates (all outdated Apps are ready to be updated at time zero), is non-preemptive (once started, the update of an App continues until it’s finished; ignoring crashes and other issues), and doesn’t involve sequence-dependent setup times (as soon as an App finishes updating, the next App in line can start its update right away). Under these circumstances, the makespan of a group of outdated Apps is always the same, regardless of the order in which they get updated. For example, if App A takes 15 seconds to download and install, and App B takes 10 seconds to download and install, it will take me 25 seconds to update both of them, regardless of which one is updated first. So far, so good. But let’s see what happens with the total (or average) completion time.

Continuing with the two-App example above, if I update the Apps in the order A, B, the completion time of A is 15, and the completion time of B is 25. The total completion time is 15+25=40, and the average completion time is 40/2=20 seconds. If the Apps are updated in the reverse order B, A, the completion time of B is 10, and the completion time of A is 25. The total completion time now is 10+25=35, and the average completion time decreases to 35/2=17.5 seconds. If there were other Apps being updated before or after the pair A, B, swapping them to make sure that B goes before A (because B takes less time) would have the same effect (the A, B swap doesn’t change the completion time of other Apps). What I just explained is called an exchange argument. It proves that whenever two Apps are out of order (in the sense that a smaller one is placed after a larger one), swapping them reduces the total/average completion time. Therefore, the minimum total/average completion time is obtained when the Apps are sorted by increasing order of duration. In the scheduling literature, this is called the SPT rule (Shortest Processing Time first).

I still haven’t answered the question of whether all of this matters because the makespan doesn’t depend on the order of Apps (updating A and B always takes 25 seconds). The answer is I don’t know! It’s a psychological effect. Shorter completion times may give the user the impression that the update process is going fast because a bunch of small Apps get updated quickly. By updating larger Apps first, the user may have the impression that the process is taking longer because, after a while, there are still many Apps to go. Should Apple worry about this? I’ll leave that question to my colleagues in the Marketing department who specialize in Consumer Behavior. If the answer turns out to be “yes”, then you now know what to do.

P.S. I’d like to know what other mobile operating systems do. Do they use SPT? Please let me know in the comments.

5 Comments

Filed under Applications, iPhone

The “Real” Reason Bill Cook Created the TSP App

By now, most people are aware of the latest Internet meme Texts from Hillary which is, by the way, hilarious. You’re also probably aware that Bill Cook created an iPhone App that allows one to solve traveling salesman problems (TSP) on a mobile phone! If you like optimization, you have to give this App a try; and make sure to check out the Traveling Salesman book too!

Inspired by Texts from Hillary I finally figured out the “real” reason why Bill Cook created the App. Here it is:

1 Comment

Filed under Applications, Books, iPhone, Meme, People, Promoting OR, Traveling Salesman Problem

INFORMS 2010 Wrap-Up

I had a very productive and fun time at the INFORMS Annual Meeting in Austin, Texas. So I thought I’d share with you some of my observations about the meeting:

  • Analytics initiative by INFORMS: great idea! I believe that we (INFORMS members) have to jump onto the Analytics bandwagon and let everyone know that we can do Analytics too! It’s all about the power of words these days (see the country’s political arena for a perfect example). Starting today, I’ll tell everyone that I can do “Advanced Prescriptive Analytics” (optimization).
  • Panel on Social Networks: it was nice to hear from some of the most popular OR bloggers and learn about their motivations, fun stories, and blogging strategies. Great job Mike and Laura!
  • John Birge‘s plenary (Omega Rho Distinguished Lecture): very informative and entertaining. The simple and powerful take-home message was: align incentives. What’s good for the employees has to be good for the company as well.
  • RAS Problem Solving Competition: Michael Trick and I (a.k.a. Team MATHY) received an honorable mention at the Railway Applications Section (RAS) 2010 Challenge (certificate + photo :-). After watching the three finalists’ presentations, we were happy to see that our solution value of $11,399,670.88 was equal to the best solution found by the winning team, and better than the solution found by the other two finalists. Nobody managed to prove optimality, though. Interestingly, none of the finalists thought about scaling the problem (thinking in terms of tanks of gasoline instead of gallons of gasoline), which made a huge difference in the performance of our model. Overall, it was a lot of fun to participate in this competition and I want to thank the organizers for putting it together. Here’s a picture of team MATHY with Juan Morales from BNSF Railway.

    And here’s a picture of the railroad network we had to deal with:

  • Technical sessions: I watched many interesting and inspiring talks (as a matter of fact, I had some great ideas for my own research while watching a number of presentations). It’s nice to see that *a lot* of people are using Latex Beamer these days. Let’s aim for a Powerpoint-free INFORMS by 2020!
  • Idea for an iPhone App? I applaud the going-green initiative of reducing the number of conference program booklets that have to be printed out. However, for this to work it requires a lot of organization from each of us: we have to go over the program in advance, select the talks we want, and print the appropriate pages. I don’t know about you, but I never manage to get this done. So I propose we create an iPhone (mobile) app to allow participants to browse the program on-the-go. It’s not convenient to browse the program PDF on a phone. We need an app. We need to be able to filter by author, by chair, by topic/keyword, etc. We want a time-sensitive app that tells you what’s next. We want an app that sends notifications to your phone reminding you that a talk/event is coming up so that you ask for the check in time. If we had something like that, I think that a lot fewer people would ask for a printed program (myself included).
  • Thumbs up for all the vegetarian food: being a vegetarian myself, I was impressed with the generous availability of vegetarian food (i.e. not only salad) at both the Sunday and Tuesday receptions. Well done!
  • Austin’s Convention Center: in addition to being huge, the convention center’s numerous under-construction areas made it very hard to navigate from session to session. I always felt like I was taking the longest path from point A to point B.
  • Meeting old and new friends: it was great to make many new friends and to meet old friends from my PhD days at Carnegie Mellon at the Tepper Alumni reception. I also had some very productive research meetings with several colleagues.

Last but not least, I’d like to thank John Hooker, Christopher Beck, and Willem-Jan van Hoeve for agreeing to give a talk in my session, and Willem for inviting me to present in his session.

Time to say bye-bye to weird Austin and fly back to Miami! Hence, I had to put on my “U” shirt:

10 Comments

Filed under Analytics, Challenge, INFORMS, iPhone, Travel

OR on the iPhone

picture-11I’m the proud owner of an iPhone (1st generation; anxiously waiting for the 3rd gen. release later this year). With all its bells and whistles and intuitive easy-to-use interface, the iPhone can also be used as an effective educational tool. The upcoming hardware and software updates promise to make it even better.

Stanford University has a computer science course entitled “iPhone Application Programming” and, guess what, they’ve made it publicly available (free of charge) from iTunesU. That includes everything: slides, homework assignments and video recordings of the lectures! It doesn’t get any better than this.

This brings me to the reason for this post: why not have an OR-related iPhone App? The possibilities are endless: from teaching the Simplex graphical method, to using the location-aware services and maps to help people navigate and meet during our gigantic INFORMS annual meetings. Incidentally, this ties in with Mike Trick’s last post on social networking technologies. I already have an App idea of my own but, for the time being, it will have to remain a secret.

The main question now becomes: what percentage of INFORMS members own an iPhone?

4 Comments

Filed under iPhone, Programming, Teaching