7. Scheduling Flashcards
describing tiplet
α field: machine environment; just one entry
β field: processing characteristics and constraints
γ field: objective to be minimized
Machine environment α
- Single machine (1)
- Identical machines in parallel (Pm)
Flow shop (Fm)
- m machines in series
- Each job has to be processed on each one of the m machines
- All jobs have to follow the same route
- After completion on one machine a job joins the queue at the next machine (Usually FIFO)
Job shop (Jm)
- each job has its own predetermined route to follow
- distinction: each job visits each machine at most
once / job may visit each machine more than once (recirculation)
Processing characteristics and constraints: β
- Release dates (rj)
- Sequence dependent setup times (sjk )
Objective: γ
- completion time
- due dates: lateness/ tardiness
Fig. Due date related penalty functions
Upper left: lateness Lj = Cj − dj (positive or negative)
Upper right: tardiness Tj = max(Lj, 0) (only positive)
Bottom: unit penalty {0, 1}
(1) Objective: minimize the sum of the completion times
Optimal solution: scheduling jobs according to non-decreasing processing times
(1) Objective: minimize total weighted completion time
Optimal solution: scheduling jobs according to the non-decreasing order of the ratio pj/wj
(1) Objective: minimize the maximum lateness
Optimal solution: scheduling jobs according to non-decreasing due dates
(Pm) Objective: minimize maximum completion time (makespan)
-> Longest Processing Time (LPT) heuristic
-> Local search heuristic
Longest Processing Time (LPT) heuristic
- start without a schedule and gradually construct a schedule by adding one job at a time
- Steps:
1. Assign at t = 0 the m longest jobs at the m machines
2. As soon as a machine gets free, assign the unscheduled job with the biggest processing time to it
Local search heuristic
- Improvement heuristic: start out with a complete schedule, which may be selected arbitrarily, and then try to obtain a better schedule by manipulating the current schedule
- does not guarantee an optimal solution
- attempts to find a schedule that is better than the current one in the neighborhood of the current one
Local search heuristic design criteria
- The schedule representation needed for the procedure
- The neighborhood design
- The search process within the neighborhood
- The acceptance-rejection criterion
Local Search Heuristic Algorithm
(Pm) Objective: minimize the sum of the completion times
Optimal solution: scheduling the jobs according to
the non-decreasing processing time
(Pm) Objective: minimize total weighted completion time
- NP-hard for m ≥ 2
- Heuristic solution method: Weighted shortest processing time (WSPT) heuristic
(Pm) Objective: minimize the maximum lateness
- NP-hard for m ≥ 2
- Heuristic solution method: Earliest Due Date (EDD) heuristic
(J2) Objective: minimize maximum completion time (Job shop models)
Optimal solution for m=2:
1. Apply Johnson’s rule to set J1. Let σ1 be the resulting sequence
2. Apply Johnson’s rule by using at first the machine 2 to set J2. Let σ2 be the resulting sequence
3. Apply the sequence σ1, σ2 on machine 1
4. Apply the sequence σ2, σ1 on machine 2
(F2) Objective: minimize maximum completion time (Flow shop models)
(m=2): Optimal solution: scheduling the jobs according to Johnson’s Rule
1 Select the job with the minimum processing time across all machines, i.e., arg min_j∈{1,…,n} pij
2 If this job concerns the first machine, execute this job as first one, otherwise as the last one
3 Delete the job
4 If jobs to schedule are left, come back to point 1
- NP-hard for m ≥ 3
