Intro Scheduling of Manufacturing Systems.pptx

It's about a brief introduction to application of scheduling in manufacturing systems

1. Scheduling of Manufacturing Systems Spring 2025

2. Contents of today’s lecture Course outlines and recommended books Introduction Importance of scheduling The role of scheduling The scheduling function in an enterprise Problem definition Visualization Deterministic model preliminaries Problem classification (α| β|γ ) Possible entries in the α, β , γ fields Solution types Classes of schedule Complexity of the scheduling problem

3. Course outlines and recommended books Introduction to scheduling of manufacturing systems Performance measures of different scheduling techniques Single machine scheduling problem Parallel machines scheduling problem Flow shop scheduling problem Job shop scheduling problem Project scheduling Genetic Algorithms applied to operations scheduling Recommended books: Scheduling (theory, algorithms and systems) Micheal L. Pinedo ii. Algorithms for Sequencing & Scheduling Ibrahim M. Al- harkan iii. Genetic Algorithms & Engineering Optimization Mitsuo Gen & Runwie Cheng

4. Introduction Importance of scheduling The role of scheduling The scheduling function in an enterprise

5. The importance of scheduling Manufacturing industries are actually like a backbone in the economic structure of a nation Productivity can be maximized if the available resources are utilized in an optimized manner Optimized utilization of resources can only be possible if there is proper scheduling system in place This makes scheduling a highly important aspect of a manufacturing system

6. The role of scheduling

7. Examples A paper bag factory Gate assignment at an airport Scheduling tasks in a Central Processing Unit (CPU)

8. Paper Bag Factory Basic raw material for such an operation are rolls of paper. Production process consists of three stages: ( i ) printing of the logo, (ii) gluing of the side of the bag, (iii) sewing of one end or both ends. Each stage consists of a number of machines which are not necessarily identical. Each production order indicates a given quantity of a specific bag that has to be produced and shipped by a committed shipping date or due date. Processing times for the different operations are proportional to the number of bags ordered. There are setup times when switching over different types of bags (colours, sizes) that depend on the similarities between the two consecutive orders A late delivery implies a penalty that depends on the importance of the order or the client and the tardiness of the delivery.

9. Gate Assignments at an Airport Airline terminal at an airport with dozens of gates and hundreds of arrivals each day. Gates and Airplanes have different characteristics Airplanes follow a certain schedule During the time the plane occupies a gate, it must go through a series of operations There is a scheduled departure time (due date) Performance measured in terms of on time departures.

10. Scheduling tasks in a Central Processing unit Multi-tasking operating system Schedule time that the CPU devotes to the different programs Exact processing time unknown but an expected value might be known Each program has a certain priority level Tasks are often sliced into little pieces. They are then rotated such that low priority tasks of short duration do not stay for ever in the system. Minimize expected time

11. The Scheduling Function in an Enterprise

12. Problem definition

13. Visualization es

14. Framework and notations Processing time ( pij ) Release date ( rj ) Due date ( dj ) Weight ( wj ) Deterministic Models: Preliminaries

15. Problem Classification A scheduling problem is described by a triplet α| β|γ α machine environment (one or two entries) β job characteristics (none or multiple entries) γ objective to be minimized (one entry)

16. Possible entries in the α -field Single machine ( 1 ) Identical machines in parallel ( pm ) Machines in parallel with different speeds ( Qm ) Unrelated machines in parallel ( Rm ) Flow shop ( Fm ) Flexible flow shop ( FFc ) Job shop ( Jm ) Flexible job shop ( FJc ) Open shop ( Om )

17. Possible entries in the β -field Release dates ( r j ) Preemptions ( prmp ) Precedence constraint ( prec ) Sequence dependent setup times ( S jk ) Job families ( fmls ) Batch processing ( batch (b) ) Breakdowns ( brkdwn )

18. Machine eligibility restriction ( M j ) Permutation ( prmu ) Blocking ( block ) No wait ( nwt ) Recirculation ( rcrc ) Possible entries in the β -field

19. Lateness ( L j = C j - d j ) Tardiness ( T j = Max { C j - d j , 0} ) Unit penalty ( U j = ) Makespan ( C max ) Maximum lateness ( L max = max ( L 1 ,…., L n )) Total weighted completion time ( Σ w j C j ) Total weighted Tardiness ( Σ w j T j ) Total weighted number of tardy jobs ( Σ w j U j ) Possible entries in the γ -field 1 if C j > d j otherwise

20. Classes of Schedules Non-Delay Schedule: A feasible schedule is called non-delay if no machine is kept idle while an operation is waiting for processing. Active Schedule: A feasible non- preemptive schedule is called active if it is not possible to construct another schedule, through changes in the order of processing on the machines, with at least one operation finishing earlier and no operation finishing later. Semi-Active Schedule: A feasible non- preemptive schedule is called semi-active if no operation can be completed earlier without changing the order of processing on any one of the machines.

21. Complexity of the Scheduling Problem The JSSP N/M/ Cmax , where N different jobs are to be processed on M different machines, then there are (N!)^ M number of alternatives A very simple problem of 5 jobs and 8 machines will give 4.3x10^16 number of alternatives. It will need over 1000 years to find its optimal solution, even with a high performance computer which can evaluate one alternative in one micro second [ Hitomi (1996), Morshed (2006)].

22. Numerical Example