GitHub PullRequestReviewCommentEvent at 2014-09-26 15:39:38
Repository: 500lines
Actor: jwm
Payload: {"action":"created","comment":{"url":"https://api.github.com/repos/aosabook/500lines/pulls/comments/18095954","id":18095954,"diff_hunk":"@@ -0,0 +1,613 @@\n+# A Flow Shop Scheduler\n+*Flow shop scheduling* is one of the most challenging and well-studied problems in operations research. Like many challenging optimization problems, finding the best solution just is not possible for problems of a practical size. In this chapter we consider the implementation of a flow shop scheduling solver that uses a technique called *local search*; a technique that allows us to find a solution that is \"pretty good\" when finding the best solution just isn't possible. The solver will continue to try and find new solutions to the problem for a given amount of time, and finishes by returning the best solution found.\n+\n+The idea behind local search is to improve heuristically an existing solution by considering similar solutions that may be a little better. The solver uses a variety of strategies to (1) try and find similar solutions, and (2) choose one that is promising to explore next. The implementation is written in Python, and has no external requirements. By leveraging some of Python's lesser-known functionality, the solver dynamically changes its search strategy during the the solving process based on what strategies work well.\n+\n+First, we provide some background material on the flow shop scheduling problem and local search techniques. We then look in detail at the general solver code and the various heuristics / neighbourhood selection strategies that we use. Next we consider the dynamic strategy selection that the solver uses to tie everything together. Finally, we conclude with a summary of the project and some lessons learned through the implementation process.\n+\n+\n+## Background\n+### Flow Shop Scheduling\n+The flow shop scheduling problem is a well-studied optimization problem in which we must determine the processing time for various tasks on a set of machines. Take for example a car manufacturer that has an assembly line where each part of the car is completed in sequence on different machines. Different orders, however, may have custom requirements making the task of painting the outside, for example, variable from one car to the next. In our example, each car is a new *job* and each part for the car is called a *task*. Every job will have the same sequence of tasks to complete.\n+\n+The objective in flow shop scheduling is to minimize the total time it takes to process all of the tasks from every job to completion. Typically, this objective is referred to as the *makespan*. This general problem has many applications, but is most related to optimizing production facilities for the construction of various commercial products.\n+\n+Every flow shop problem consists of *n* machines and *m* jobs. Each job is made up of exactly *n* tasks, and we can assume that the *i*-th task of a job must use machine *i* and requires a predetermined amount of processing time: *p*(*j*,*i*) is the processing time for the *i*-th task of job *j*. Further, the order of the tasks for any given job should follow the order of the machines available -- for a given job, task *i* must be completed prior to the start of task *i*+1. The final restriction is that no two tasks can be processed on a machine simultaneously.","path":"flow-shop/chapter.md","position":15,"original_position":15,"commit_id":"f8f8cddb0414334af874ef4cd01b18204f88964d","original_commit_id":"f8f8cddb0414334af874ef4cd01b18204f88964d","user":{"login":"jwm","id":37176,"avatar_url":"https://avatars.githubusercontent.com/u/37176?v=2","gravatar_id":"","url":"https://api.github.com/users/jwm","html_url":"https://github.com/jwm","followers_url":"https://api.github.com/users/jwm/followers","following_url":"https://api.github.com/users/jwm/following{/other_user}","gists_url":"https://api.github.com/users/jwm/gists{/gist_id}","starred_url":"https://api.github.com/users/jwm/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jwm/subscriptions","organizations_url":"https://api.github.com/users/jwm/orgs","repos_url":"https://api.github.com/users/jwm/repos","events_url":"https://api.github.com/users/jwm/events{/privacy}","received_events_url":"https://api.github.com/users/jwm/received_events","type":"User","site_admin":false},"body":"I tripped over this formal problem definition a little bit. I'm not always the best at parsing things like this, and tend to grok a bit faster if there's an accompanying example. You do this later on, and I think your diagrams are great. Maybe adding a small, concrete example would help, such as a job that consists of two or three tasks on a car assembly line.\r\n\r\nOr, I think some small changes to the variable naming might help - could it be \"m machines and n jobs\"?","created_at":"2014-09-26T15:39:38Z","updated_at":"2014-09-26T15:39:38Z","html_url":"https://github.com/aosabook/500lines/pull/78#discussion_r18095954","pull_request_url":"https://api.github.com/repos/aosabook/500lines/pulls/78","_links":{"self":{"href":"https://api.github.com/repos/aosabook/500lines/pulls/comments/18095954"},"html":{"href":"https://github.com/aosabook/500lines/pull/78#discussion_r18095954"},"pull_request":{"href":"https://api.github.com/repos/aosabook/500lines/pulls/78"}}},"pull_request":{"url":"https://api.github.com/repos/aosabook/500lines/pulls/78","id":19897679,"html_url":"https://github.com/aosabook/500lines/pull/78","diff_url":"https://github.com/aosabook/500lines/pull/78.diff","patch_url":"https://github.com/aosabook/500lines/pull/78.patch","issue_url":"https://api.github.com/repos/aosabook/500lines/issues/78","number":78,"state":"open","locked":false,"title":"New draft for the flow-shop chapter.","user":{"login":"haz","id":225019,"avatar_url":"https://avatars.githubusercontent.com/u/225019?v=2","gravatar_id":"","url":"https://api.github.com/users/haz","html_url":"https://github.com/haz","followers_url":"https://api.github.com/users/haz/followers","following_url":"https://api.github.com/users/haz/following{/other_user}","gists_url":"https://api.github.com/users/haz/gists{/gist_id}","starred_url":"https://api.github.com/users/haz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/haz/subscriptions","organizations_url":"https://api.github.com/users/haz/orgs","repos_url":"https://api.github.com/users/haz/repos","events_url":"https://api.github.com/users/haz/events{/privacy}","received_events_url":"https://api.github.com/users/haz/received_events","type":"User","site_admin":false},"body":"Latest changes according to feedback from @mdibernardo and a completed chapter draft.","created_at":"2014-08-18T03:15:07Z","updated_at":"2014-09-26T15:39:38Z","closed_at":null,"merged_at":null,"merge_commit_sha":"3b66ec9995b6c7141c5f561c877a0ce22c1d1495","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/aosabook/500lines/pulls/78/commits","review_comments_url":"https://api.github.com/repos/aosabook/500lines/pulls/78/comments","review_comment_url":"https://api.github.com/repos/aosabook/500lines/pulls/comments/{number}","comments_url":"https://api.github.com/repos/aosabook/500lines/issues/78/comments","statuses_url":"https://api.github.com/repos/aosabook/500lines/statuses/f8f8cddb0414334af874ef4cd01b18204f88964d","head":{"label":"haz:master","ref":"master","sha":"f8f8cddb0414334af874ef4cd01b18204f88964d","user":{"login":"haz","id":225019,"avatar_url":"https://avatars.githubusercontent.com/u/225019?v=2","gravatar_id":"","url":"https://api.github.com/users/haz","html_url":"https://github.com/haz","followers_url":"https://api.github.com/users/haz/followers","following_url":"https://api.github.com/users/haz/following{/other_user}","gists_url":"https://api.github.com/users/haz/gists{/gist_id}","starred_url":"https://api.github.com/users/haz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/haz/subscriptions","organizations_url":"https://api.github.com/users/haz/orgs","repos_url":"https://api.github.com/users/haz/repos","events_url":"https://api.github.com/users/haz/events{/privacy}","received_events_url":"https://api.github.com/users/haz/received_events","type":"User","site_admin":false},"repo":{"id":14216497,"name":"500lines","full_name":"haz/500lines","owner":{"login":"haz","id":225019,"avatar_url":"https://avatars.githubusercontent.com/u/225019?v=2","gravatar_id":"","url":"https://api.github.com/users/haz","html_url":"https://github.com/haz","followers_url":"https://api.github.com/users/haz/followers","following_url":"https://api.github.com/users/haz/following{/other_user}","gists_url":"https://api.github.com/users/haz/gists{/gist_id}","starred_url":"https://api.github.com/users/haz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/haz/subscriptions","organizations_url":"https://api.github.com/users/haz/orgs","repos_url":"https://api.github.com/users/haz/repos","events_url":"https://api.github.com/users/haz/events{/privacy}","received_events_url":"https://api.github.com/users/haz/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/haz/500lines","description":"500 Lines or Less","fork":true,"url":"https://api.github.com/repos/haz/500lines","forks_url":"https://api.github.com/repos/haz/500lines/forks","keys_url":"https://api.github.com/repos/haz/500lines/keys{/key_id}","collaborators_url":"https://api.github.com/repos/haz/500lines/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/haz/500lines/teams","hooks_url":"https://api.github.com/repos/haz/500lines/hooks","issue_events_url":"https://api.github.com/repos/haz/500lines/issues/events{/number}","events_url":"https://api.github.com/repos/haz/500lines/events","assignees_url":"https://api.github.com/repos/haz/500lines/assignees{/user}","branches_url":"https://api.github.com/repos/haz/500lines/branches{/branch}","tags_url":"https://api.github.com/repos/haz/500lines/tags","blobs_url":"https://api.github.com/repos/haz/500lines/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/haz/500lines/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/haz/500lines/git/refs{/sha}","trees_url":"https://api.github.com/repos/haz/500lines/git/trees{/sha}","statuses_url":"https://api.github.com/repos/haz/500lines/statuses/{sha}","languages_url":"https://api.github.com/repos/haz/500lines/languages","stargazers_url":"https://api.github.com/repos/haz/500lines/stargazers","contributors_url":"https://api.github.com/repos/haz/500lines/contributors","subscribers_url":"https://api.github.com/repos/haz/500lines/subscribers","subscription_url":"https://api.github.com/repos/haz/500lines/subscription","commits_url":"https://api.github.com/repos/haz/500lines/commits{/sha}","git_commits_url":"https://api.github.com/repos/haz/500lines/git/commits{/sha}","comments_url":"https://api.github.com/repos/haz/500lines/comments{/number}","issue_comment_url":"https://api.github.com/repos/haz/500lines/issues/comments/{number}","contents_url":"https://api.github.com/repos/haz/500lines/contents/{+path}","compare_url":"https://api.github.com/repos/haz/500lines/compare/{base}...{head}","merges_url":"https://api.github.com/repos/haz/500lines/merges","archive_url":"https://api.github.com/repos/haz/500lines/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/haz/500lines/downloads","issues_url":"https://api.github.com/repos/haz/500lines/issues{/number}","pulls_url":"https://api.github.com/repos/haz/500lines/pulls{/number}","milestones_url":"https://api.github.com/repos/haz/500lines/milestones{/number}","notifications_url":"https://api.github.com/repos/haz/500lines/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/haz/500lines/labels{/name}","releases_url":"https://api.github.com/repos/haz/500lines/releases{/id}","created_at":"2013-11-07T21:32:57Z","updated_at":"2014-07-23T05:03:16Z","pushed_at":"2014-08-21T22:28:58Z","git_url":"git://github.com/haz/500lines.git","ssh_url":"git@github.com:haz/500lines.git","clone_url":"https://github.com/haz/500lines.git","svn_url":"https://github.com/haz/500lines","homepage":null,"size":9079,"stargazers_count":0,"watchers_count":0,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"aosabook:master","ref":"master","sha":"ccaeedf1676aed429ce3e4c5782e1ee4049feba3","user":{"login":"aosabook","id":5631751,"avatar_url":"https://avatars.githubusercontent.com/u/5631751?v=2","gravatar_id":"","url":"https://api.github.com/users/aosabook","html_url":"https://github.com/aosabook","followers_url":"https://api.github.com/users/aosabook/followers","following_url":"https://api.github.com/users/aosabook/following{/other_user}","gists_url":"https://api.github.com/users/aosabook/gists{/gist_id}","starred_url":"https://api.github.com/users/aosabook/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aosabook/subscriptions","organizations_url":"https://api.github.com/users/aosabook/orgs","repos_url":"https://api.github.com/users/aosabook/repos","events_url":"https://api.github.com/users/aosabook/events{/privacy}","received_events_url":"https://api.github.com/users/aosabook/received_events","type":"User","site_admin":false},"repo":{"id":14098121,"name":"500lines","full_name":"aosabook/500lines","owner":{"login":"aosabook","id":5631751,"avatar_url":"https://avatars.githubusercontent.com/u/5631751?v=2","gravatar_id":"","url":"https://api.github.com/users/aosabook","html_url":"https://github.com/aosabook","followers_url":"https://api.github.com/users/aosabook/followers","following_url":"https://api.github.com/users/aosabook/following{/other_user}","gists_url":"https://api.github.com/users/aosabook/gists{/gist_id}","starred_url":"https://api.github.com/users/aosabook/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aosabook/subscriptions","organizations_url":"https://api.github.com/users/aosabook/orgs","repos_url":"https://api.github.com/users/aosabook/repos","events_url":"https://api.github.com/users/aosabook/events{/privacy}","received_events_url":"https://api.github.com/users/aosabook/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/aosabook/500lines","description":"500 Lines or Less","fork":false,"url":"https://api.github.com/repos/aosabook/500lines","forks_url":"https://api.github.com/repos/aosabook/500lines/forks","keys_url":"https://api.github.com/repos/aosabook/500lines/keys{/key_id}","collaborators_url":"https://api.github.com/repos/aosabook/500lines/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/aosabook/500lines/teams","hooks_url":"https://api.github.com/repos/aosabook/500lines/hooks","issue_events_url":"https://api.github.com/repos/aosabook/500lines/issues/events{/number}","events_url":"https://api.github.com/repos/aosabook/500lines/events","assignees_url":"https://api.github.com/repos/aosabook/500lines/assignees{/user}","branches_url":"https://api.github.com/repos/aosabook/500lines/branches{/branch}","tags_url":"https://api.github.com/repos/aosabook/500lines/tags","blobs_url":"https://api.github.com/repos/aosabook/500lines/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/aosabook/500lines/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/aosabook/500lines/git/refs{/sha}","trees_url":"https://api.github.com/repos/aosabook/500lines/git/trees{/sha}","statuses_url":"https://api.github.com/repos/aosabook/500lines/statuses/{sha}","languages_url":"https://api.github.com/repos/aosabook/500lines/languages","stargazers_url":"https://api.github.com/repos/aosabook/500lines/stargazers","contributors_url":"https://api.github.com/repos/aosabook/500lines/contributors","subscribers_url":"https://api.github.com/repos/aosabook/500lines/subscribers","subscription_url":"https://api.github.com/repos/aosabook/500lines/subscription","commits_url":"https://api.github.com/repos/aosabook/500lines/commits{/sha}","git_commits_url":"https://api.github.com/repos/aosabook/500lines/git/commits{/sha}","comments_url":"https://api.github.com/repos/aosabook/500lines/comments{/number}","issue_comment_url":"https://api.github.com/repos/aosabook/500lines/issues/comments/{number}","contents_url":"https://api.github.com/repos/aosabook/500lines/contents/{+path}","compare_url":"https://api.github.com/repos/aosabook/500lines/compare/{base}...{head}","merges_url":"https://api.github.com/repos/aosabook/500lines/merges","archive_url":"https://api.github.com/repos/aosabook/500lines/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/aosabook/500lines/downloads","issues_url":"https://api.github.com/repos/aosabook/500lines/issues{/number}","pulls_url":"https://api.github.com/repos/aosabook/500lines/pulls{/number}","milestones_url":"https://api.github.com/repos/aosabook/500lines/milestones{/number}","notifications_url":"https://api.github.com/repos/aosabook/500lines/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/aosabook/500lines/labels{/name}","releases_url":"https://api.github.com/repos/aosabook/500lines/releases{/id}","created_at":"2013-11-04T02:02:53Z","updated_at":"2014-09-26T05:03:46Z","pushed_at":"2014-09-08T20:59:53Z","git_url":"git://github.com/aosabook/500lines.git","ssh_url":"git@github.com:aosabook/500lines.git","clone_url":"https://github.com/aosabook/500lines.git","svn_url":"https://github.com/aosabook/500lines","homepage":null,"size":34728,"stargazers_count":2132,"watchers_count":2132,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":359,"mirror_url":null,"open_issues_count":27,"forks":359,"open_issues":27,"watchers":2132,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/aosabook/500lines/pulls/78"},"html":{"href":"https://github.com/aosabook/500lines/pull/78"},"issue":{"href":"https://api.github.com/repos/aosabook/500lines/issues/78"},"comments":{"href":"https://api.github.com/repos/aosabook/500lines/issues/78/comments"},"review_comments":{"href":"https://api.github.com/repos/aosabook/500lines/pulls/78/comments"},"review_comment":{"href":"https://api.github.com/repos/aosabook/500lines/pulls/comments/{number}"},"commits":{"href":"https://api.github.com/repos/aosabook/500lines/pulls/78/commits"},"statuses":{"href":"https://api.github.com/repos/aosabook/500lines/statuses/f8f8cddb0414334af874ef4cd01b18204f88964d"}}}}