Task SchedulingAbout This PresentationMini-Sudoku PuzzleMini-Sudoku Puzzle: Solution MethodSudoku Puzzle: Easy ExampleSudoku Puzzle Solution MethodSudoku Puzzle: Hard ExampleVariations on SudokuTask Scheduling ProblemResource Allocation ProblemScheduling Required CE CoursesSlide 12Job-Shop SchedulingTruck SchedulingMultiprocessor SchedulingAssignment to ProcessorsMay 2007 Task Scheduling Slide 1Task SchedulingA Lecture in CE Freshman Seminar Series:Ten Puzzling Problems in Computer EngineeringMay 2007 Task Scheduling Slide 2About This PresentationEdition Released Revised RevisedFirst May 2007This presentation belongs to the lecture series entitled “Ten Puzzling Problems in Computer Engineering,” devised for a ten-week, one-unit, freshman seminar course by Behrooz Parhami, Professor of Computer Engineering at University of California, Santa Barbara. The material can be used freely in teaching and other educational settings. Unauthorized uses, including any use for financial gain, are prohibited. © Behrooz ParhamiMay 2007 Task Scheduling Slide 3Mini-Sudoku PuzzleComplete entries in this chart so that numbers 1-6 appear without repetition in each row, each column and each 2  3 blockUSA Today carries a daily mini-Sudoku at its site:http://puzzles.usatoday.com Standard Sudoku consists of a 9  9 chart, but this mini version is good for a quick fix24 16 3513 64 63Sudoku isn’t a math puzzle: Can substitute letters A-F or any other six symbols for numbers 1-6May 2007 Task Scheduling Slide 4Mini-Sudoku Puzzle: Solution MethodComplete entries in this chart so that letters A-F appear without repetition in each row, each column and each 2  3 blockTo continue from here, write down all possible choices in the remaining blank boxes and see whether the resulting info leads to more progressC24C16BDA3513 D 64 C 6 A3 DDBD AF CEAC FD FCSuDoKu: abbr. in Japanese for “numbers must be single.” Euler may have invented it; Howard Garns (US) & Wayne Gould (HK) popularized it in modern timesMay 2007 Task Scheduling Slide 5Sudoku Puzzle: Easy Example54 76 7 49 526 136 498571 362 988 35 9 74 56Complete entries in this chart so that numbers 1-9 appear without repetition in each row, each column and each 3  3 blockSudoku puzzles of varying difficulties (easy, medium, hard, evil) are available athttp://www.websudoku.comand several other Web sites, such as USA Today’s sitehttp://puzzles.usatoday.com Many newspapers carry these puzzles; there are also many collections in book formMay 2007 Task Scheduling Slide 6Sudoku Puzzle Solution Method54 76 7 49 526 136 498571 362 988 35 9 74 568Strategy 1: Identify a missing number from a row, column, or block; if you can exclude all but one cell for that number, then write it down67Strategy 2: When you can’t make progress by Strategy 1, write down all candidate numbers in the cells and try to eliminate a number of options via reasoning. For example if xy, xy, xyz are candidates in three cells of a block, then the cell marked xyz must hold z6 17 9358 582214 942525282871314 2323141, 2, 3, 4 missing from this row7, 8, 9 missing from this column17391May 2007 Task Scheduling Slide 7Sudoku Puzzle: Hard Example416 8556 43 9542117 98 5939 612Complete entries in this chart so that numbers 1-9 appear without repetition in each row, each column and each 3  3 blockHard puzzles typically have fewer entries supplied, with each row, column, or block containing only a few entriesHard puzzles may have handles or starting points (5 in the top left block or 9 in center and lower right blocks)May 2007 Task Scheduling Slide 8Variations on SudokuOther sizes (e.g., 6  6, with 2  3 blocks; or 16  16, with 4  4 blocks)Combining this 2000s phenomenon with Rubik’s cube of the 1980s . . .or with the age-old sliding 15 puzzleMay 2007 Task Scheduling Slide 9Task Scheduling ProblemWe have a set of of tasks Numbers in Sudoku puzzleThere are some “processors” that can execute tasksCells in Sudoku puzzle can hold numbersAssign tasks to processors so as to meet certain constraintsPlace numbers in cells while honoring some constraintsA task may fit only some processorsTasks may have prerequisites tasksPreemption may (not) be allowedTasks may have deadlinesShortest schedule may be requiredUse only numbers 1-9Some numbers already placedDifferent numbers in each rowDifferent numbers in each columnDifferent numbers in each blockVirtually all instances of the task scheduling problem are difficult (NP-complete), just like SudokuMay 2007 Task Scheduling Slide 10Resource Allocation ProblemWe have a set of of resources Numbers in Sudoku puzzleThere are “locations” where resources may be placedCells in Sudoku puzzle can hold numbersAssign resources to locations to meet certain constraintsPlace numbers in cells while honoring some constraintsA resource may fit only some locationsResources must be “easily” accessibleResource mobility may (not) be allowedResource cost may differ by locationLowest-cost assignment may be requiredUse only numbers 1-9Some numbers already placedDifferent numbers in each rowDifferent numbers in each columnDifferent numbers in each blockVirtually all instances of the resource allocation problem are difficult (NP-complete), just like SudokuMay 2007 Task Scheduling Slide 11Scheduling RequiredCE CoursesConstraintsPrerequisite: Solid downward arrowCorequisite: Dashed sideways arrowUnits per quarter:  18 ECE 1CS 130AECE 15AECE 15BCS 170Math 3AMath 3BMath 3CMath 5ACS 10CS 20CS 40 CS 60Phys 1Phys 2Phys 3Phys 4Phys 3LPhys 4LChem 1AChem 1BChem 1ALChem 1BLECE 2AECE 2BECE 2CECE 152AECE 152BECE 15412345UnitsEngr 101Upper -division standingECE 139Or CS 30Or PSTAT 120AOr CS 3012 units20 unitsMay 2007 Task Scheduling Slide 12Scheduling Required CE CoursesConstraintsPrerequisite: Solid downward arrowCorequisite: Dashed sideways arrowUnits per quarter:  18 ECE 1CS 130AECE 15AECE 15BCS 170Math 3AMath 3BMath 3CMath 5ACS 10CS 20CS 40 CS 60Phys 1Phys 2Phys 3Phys 4Phys 3LPhys 4LChem 1AChem 1BChem 1ALChem 1BLECE 2AECE 2BECE 2CECE 152AECE 152BECE 15412345UnitsEngr 101Upper -division standingECE 139Or CS 30Or PSTAT 120AOr CS 30Almost done!12 units20 units16May 2007 Task Scheduling Slide 13Job-Shop SchedulingTime0 2 4 6 8 10 12 140246Staff8Tb1 Tc1Ta1Ta2Tb2Td2Tb3Td1Job Task Machine Time Staff Ja Ta1 M1 2 3 Ja Ta2 M3 6 2 Jb Tb1 M2 5 2 Jb Tb2 M1 3 3 Jb Tb3 M2 3 2 Jc Tc1 M3 4 2 Jd Td1 M1 5 4 Jd