PRODUCTION SCHEDULING2.Penjadwalan produksi

Penjadawalan Produksi

1. PENJADWALAN PRODUKSIPENJADWALAN PRODUKSI
… Makes on time delivery possible …

2. CAKUPAN BAHASAN
•Tujuan penjadwalan produksi.
•Pendekatan terhadap persoalan penjadwalan.
•Ukuran baku dalam penjadwalan.
•Review pendekatan penjadwalan traditional.
•Mengapa persoalan penjadwalan sulit?
•Mengembangkan pendekatan penjadwalan
praktis:
–The bottleneck resource.
–The entire plant.

3. ILUSTRASI AGROINDUSTRI GULAILUSTRASI AGROINDUSTRI GULA
X% Kandungan gula
X’% Kandungan gula
X’’% RendemenDimana: X’’ < X’ < X
Fungsi Tujuan: Min X-X’; X’-X’’

4. Tujuan Penjadwalan Produksi
•Menepati waktu jatuh tempo (due dates)
•Memaksimumkan penggunaan fasilitas
•Menurunkan WIP dan siklus waktu (Cycle Times)
 Tujuan-tujuan ini saling konflik
The goal of production scheduling is to strike a
profitable balance among these conflicting objectives

5. Menepati Due Dates
•Dalam sistem make-to-order, due date dari
customer akan mempengaruhi semua due
dates.
•Dalam sistem make-to-stock, tingkat
persediaan (inventory level) memicu
produksi di bagian produksi (manufacturing
system)

6. Terminologi
•Service level (also known as simply service),
biasanya digunakan dalam sistem make-to-order,
adalah fraksi dari order yang ditepati pada atau
sebelum jatuh tempo (due dates). Atau, adalah
fraksi dari pekerjaan (jobs) dengan cycle time
kurang dari atau sama dengan perkiraan lead time.
•Fill rate adalah service level dalam sistem make-
to-stock, yaitu fraksi dari demand yang dapat
mengisi inventory tanpa backorder.

7. Terminologi …
•Lateness adalah selisih antara waktu jatuh tempo
order dengan waktu selesainya (completion) suatu
pekerjaan. Jika d
j
adalah due date dan c
j
adalah
waktu selesainya pekerjaan j, maka lateness dari
pekerjaan j adalah L
j = c
j -d
j .
•Lateness bisa bernilai positive (menunjukkan
pekerjaan yang terlambat) atau negative
(menunjukkan pekerjaan yang cepat)  Bad in
average.

8. Terminologi …
•Tardiness adalah lateness dari suatu
pekerjaan jika pekerjaan itu terlambat,
atau 0 jika tidak.
•Jadi, suatu pekerjaan yang cepat
memiliki nilai tardiness nol  average
tardiness dianggap ukuran yang lebih
bermakna untuk menilai kinerja waktu
jatuh tempo.

9. Memaksimumkan Penggunaan
•Tingkat penggunaan yang tinggi dari barang-barang
modal berarti return on investment tinggi, jika
barang-barang modal tersebut didayagunakan untuk
meningkatkan revenue (i.e., to create products that
are in demand).
•Jika tidak, tingkat penggunaan yang tinggi hanya
untuk meningkatkan inventory, bukan profits.
•Ukuran yang biasa digunakan untuk pendayagunaan
barang-barang modal adalah makespan, yaitu waktu
yang diperlukan untuk menyelesaikan sejumlah
pekerjaan yang telah ditetapkan.

10. Menurunkan WIP dan Cycle Times
Keuntungan cycle time yang pendek:
–Better responsiveness to the customer.
–Maintaining flexibility.
–Improving quality.
–Relying less on forecasts.
–Making better forecasts.

11. Classic Scheduling
Penyederhanaan asumsi:
•Semua pekerjaan telah tersedia pada saat mulai
produksi (i.e., no jobs arrive after processing
begins).
•Lama waktu proses pekerjaan telah diketahui
dengan pasti (deterministic).
•Lama waktu proses tidak tergantung pada jadwal
(i.e., there are no setups).
•Mesin dan peralatan tidak pernah mogok.
•Tidak ada pekerjaan pendahuluan (preemption)
(i.e., once a job starts processing, it must finish).
•Tidak ada pekerjaan yang dibatalkan.

12. Classic Scheduling …
•Tujuan penjadwalan:
–Minimisasi rata-rata cycle time pada mesin
tunggal.
–Minimisasi maksimum lateness pada mesin
tunggal.
–Minimisasi rata-rata tardiness pada mesin
tunggal.
–Minimisasi makespan pada dua mesin.
–Minimisasi makespan pada job shops.

13. Mempercepat (Dispatching)
•Persoalan penjadwalan adalah persoalan
yang sulit, baik secara teori maupun praktek.
•Alternatif menyederhanakan adalah dengan
cara mempercepat proses sesuai dengan
urutan tertentu pada saat tiba di depan mesin
untuk diproses:
- The first-in, first-out (FIFO).
- The earliest due date (EDD).
- The shortest process time (SPT).
- Many more …

14. Mengapa Penjadwalan Sulit?
•Melibatkan jumlah bilangan yang banyak.
•Problem Classes:
- Class P problems are problems that can
be solved by algorithms whose
computational time grows as a polynomial
function of problem size  Easy.
- NP-hard problems are problems for
which there is no known polynomial algorithm,
so that the time to find a solution grows
exponentially  Hard.

15. Why Scheduling Is Hard
Exponential
problems

16. Why Scheduling Is Hard…
Polynomial
problems

17. Heuristic
•Telah banyak dikembangkan metode
heuristics untuk penjadwalan, antara lain:
–Beam search,
–Tabu search,
–Simulated annealing, dan
–Genetic algorithms.

18. Bad News
•There are always more than two machines. Thus
Johnson's minimizing makespan algorithm and its
many variants are not directly useful.
•Process times are not deterministic. Randomness
and variability contribute greatly to the congestion
found in manufacturing systems. By ignoring this,
scheduling theory may have overlooked
something fundamental.

19. Bad News …
•All jobs are not ready at the beginning of
the problem. New jobs do arrive and
continue arriving during the entire life of
the plant. To pretend that this does not
happen or to assume that we "clear out" the
plant before starting new work is to deny a
fundamental aspect of plant behavior.

20. Bad News …
•Process times are frequently sequence-
dependent. Often the number of setups
performed depends on the sequence of the
jobs. Jobs of like or similar parts can
usually share a setup while dissimilar jobs
cannot. This can be an important concern
when scheduling the bottleneck process.

21. Good News
•The constraints assumed in the models are
not necessarily fixed in the real world since,
to some extent, we can control the problem
by controlling the environment.
•This is precisely what the Japanese did
when they made a hard scheduling problem
much easier by reducing setup times.

22. Good News …
•Due dates: We do have some control
over due dates; after all, someone in the
company sets or negotiates them. We do
not have to take them as given, although
this is exactly what some companies and
most scheduling problem formulations
do.

23. Good News …
•Job splitting: The SPT results for a single
machine suggest that small jobs clear out more
quickly than large jobs. Similarly, the
mechanics of Johnson's algorithm call for a
sequence that has a small job at both the
beginning and the end. Thus, it appears that
small jobs will generally improve performance
with regard to average cycle time and machine
utilization.

24. Good News …
•Feasible schedules: An optimal schedule is
really only meaningful in a mathematical
model. In practice what we need is a good,
feasible one.
•Focus on bottlenecks: It is typically most
critical to schedule these resources.
•Capacity: As with due dates, we have some
control over capacity. We can use some
capacity controls (e.g., overtime) on the same
time frame as that used to schedule production.

25. Example
•To illustrate the difficulty of the
problem and to suggest a solution
approach, we consider 16 jobs.
•Each job takes one hour to
complete, not including a setup.
Setups take four hours and occur
if we go from any job family to
any other.
•The jobs are arranged in earliest
due date order.
•As we see, EDD does not appear
very effective here, since it
results in 10 setups and 12 tardy
jobs for an average tardiness of
10.4.
•To find an optimal one, we have
to evaluate 16! = 2 x 10
13
possible
sequences.

26. Greedy Algorithm
•Each step of a greedy
algorithm considers all simple
alternatives (i.e., pairwise
interchanges of jobs in the
sequence) and selects the one
that improves the schedule the
most.
•Checking the total tardiness
for every possible exchange
between two jobs in the
sequence reveals that the
biggest decrease is achieved
by putting job 4 after job 5.
•As shown, this eliminates two
setups (going from family 1 to
family 2 and back again). The
average tardiness is now 5.0
with eight setups.

27. Greedy Algorithm …
•We repeat the procedure in the
second step of the algorithm.
•This time, the biggest reduction
in total tardiness results from
moving job 7 after job 8.
•Again, this eliminates two
setups by grouping like families
together.
•The average tardiness falls to
1.2 with six setups.
•The third step moves job 10
after job 12, which eliminates
one setup and reduces the
average tardiness to one-half.
The resulting sequence is
shown in Table 15.7.

28. Tabu Search
•The greedy algorithms can quickly
converge to a local optimum-a
solution that is better than any
other adjacent solutions, but not as
good as a nonadjacent solution.
•This is particularly likely because
NP-hard problems like this one
tend to have many local optima.
•What we need is a mechanism that
will force the algorithm away
from a local optimum in order to
see if there are better sequences
farther away.
•One way to do this is to prohibit
(make "taboo") certain recently
considered moves. This approach
is called tabu search.

29. Shop Floor Scheduling
How long does it take?
Processing times of
workers on activities
Figure: Activity Network
1
2
3
4
5
6
7
8
9
Activitie
s
Workers
A BC
1 2 34
2 4 2 -
3 - 56
4 7 76
5 5 -4
6 3 32
7 2 -4
8 - 67
9 8 67