22nd International Joint Conference on Artificial Intelligence (IJCAI), Barcelona 2011

Adventures in Scheduling: Some Trends in Operations Research

author: Michael Trick, Tepper School of Business, Carnegie Mellon University
published: Aug. 23, 2011, recorded: July 2011, views: 638

Slides

Slides
0:00	Adventures in Scheduling: Some Trends in Operations Research - 1
1:22	Adventures in Scheduling: Some Trends in Operations Research - 2
1:39	Picture - 1
2:30	The History Starts in 1995
3:23	History
4:06	The Competition
4:41	Why is this interesting? - 1
5:39	Why is this interesting? - 2
7:17	Interesting fomulation
7:36	Important problem
8:33	Computationally Difficult Problem
9:23	Traveling Tournament Problem
9:55	Sample Instance
10:01	Sample Solution
10:51	Simple Problem, yes?
11:25	10 years of progress on NL12
11:51	2005 SCHEDULE
12:05	SI Exclusive
12:38	2008 SCHEDULE
12:44	Picture - 2
13:18	Story to be continued
14:05	Outline
14:25	General Trends
14:52	Increased Data
15:22	Big Spending
15:52	OR Role
16:03	Faster Computers: Supercomputer and otherwise
17:15	Faster computers increases the relevance and applicability of OR
17:36	Algorithms are getting better also!
18:20	Speed
19:02	Illustration: TSP with 2392 nodes
19:46	Current Trends in Operations Research (with an IP focus)
20:37	Current Trend 1: General IP Improvements, not Problem Specific Ones
22:05	Example - 1
23:10	2005
24:07	2005 solution - 1
25:02	2005 solution - 2
25:57	2009 solution
26:52	Subtle but important change
27:12	Current Trend 2: More complicated variables
28:11	Formulations
29:03	Better formulation
29:29	Variables
29:49	Constraints - 1
29:56	Constraints - 2
30:02	Linking Constraints
30:25	Results
30:51	More complicated variables
31:14	Current Trend 3: Linking Models
32:20	Back to 1962
32:39	General idea
33:41	Example - 2
33:59	Problem A: Find HAPs
34:04	Problem B. Assign Games
34:21	Iterating
34:30	Assigning teams to patterns
35:44	Results
36:11	Benders
36:32	Current Trend 4: Large Scale Neighborhood search
37:17	Large Scale Neighborhood Search
37:43	Lots to play around with
37:48	Large Neighborhood Search
38:10	Result for MLB
38:48	Challenge Trends
39:34	Challenge Trend 1: Prescriptive and Predive Analytics Example
40:11	Capacity Planning
40:15	Problem
41:02	Business Analytics Approach to Capacity planning
42:20	Other Examples
42:30	Challenge Trend 2: Handling Uncertainty and Robustness
43:03	True measures of robustness?
44:25	Measure of Robustness
45:43	Data-free Robustness
46:07	Other applications?
47:02	Challenge Trend 3: Parallelism
47:09	Other applications?
47:12	Challenge Trend 3: Parallelism
47:57	Risk for some types of operations research
48:30	Effect on Mixed Integer Programming
49:04	Challenges
49:09	Challenge Trend 4: Adversaries
50:10	Which is where Operations Research started
50:28	Summary: Trends
51:14	Back to the story
51:15	August 2007
51:35	Picture - 2
51:56	Picture - 3
52:13	Picture - 4
52:57	Picture - 5
53:37	Picture - 6
53:43	N.Y./Region
53:53	Series Schedule - 1
53:57	Series Schedule - 2
54:05	Takeaways

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Lecture popularity: You need to login to cast your vote.

Description

Major League Baseball is a multi-billion dollar per year industry that relies heavily on the quality of its schedule. Teams, fans, TV networks, and even political parties (in a way revealed in the talk) rely on the schedule for profits and enjoyment. Only recently have the computational tools of operations research been powerful enough to address the issue of finding "optimal" schedules.