Lesson Resource Scheduling Problem - Artificial Intelligence - ثالث ثانوي

Lesson 2 Resource Scheduling Problem Link to digital lesson www.ien.edu.sa Scheduling Problems Scheduling problems are common in the optimization field as they require the allocation of limited resources to multiple tasks in a way that optimizes some objective function. Scheduling problems often have additional constraints, such as requiring tasks to happen in a specific order or to be completed by a certain deadline. These problems are essential in various real-world applications, including manufacturing, transportation, healthcare, and project management. In this lesson, we will go deeper into optimization algorithms by introducing additional techniques to solve scheduling problems. Table 5.1: Real-world applications needing scheduling solutions Application Project scheduling Function Allocate resources and tasks to project activities to minimize project duration and costs. Production planning Determine the optimal production plan to meet demand while minimizing inventory and costs. Airline scheduling Schedule aircraft departures and crew shifts to optimize flight schedules while minimizing costs and delays. Call center scheduling Allocate agents to shifts to ensure adequate coverage for working periods while minimizing costs and meeting service level agreements. Job shop scheduling Media scheduling Nurse scheduling Allocate resources in manufacturing to minimize production time and costs. Schedule the timing of advertisements on television or radio to maximize audience reach and revenue, while respecting budget constraints. Assign nurses to shifts in a hospital to ensure adequate coverage during working periods while minimizing labor costs. Project ID: 01234 Resource Project Progress 100% Charter 100% 100% 78% Week 01 View Week 02 Week 03 Week 04 Week 05 Week 06 Week (IT MTWTFMTWTFMTWTFMTWTFMTWTFMTWTFMTW! وزارة التعليم Ministry of Education 2024-1446 80% 80% 75% 0% Figure 5.3: A Gantt chart showing a project schedule 267

In this lesson, the Single-Machine Weighted Tardiness (SMWT) problem will be used as a working example to demonstrate how optimization algorithms can solve scheduling problems. Single-Machine Weighted Tardiness (SMWT) Problem To illustrate the problem, consider a factory that needs to schedule the production tasks of several items on a single machine. • Each job has a specific processing time and a due date by which it needs to be completed. Each job is also associated with a weight, which represents the job's importance. If it is impossible to complete all tasks by the deadline, it will be less expensive to miss the deadline for low-weight tasks than for high-weight tasks. Goal The goal is to schedule the jobs in a way that minimizes the weighted sum of the lateness (tardiness) of each job. The weight tardiness sum thus serves as the objective function for optimization algorithms designed to solve this problem. Lateness calculation The lateness of a job is calculated as the difference between its completion time and its due time. Job weights are then used as multipliers to complete the final weighted sum. For example, consider a schedule with three jobs, J1, J2, and J3, with weights equal to 2, 1, and 2, respectively. According to the schedule below, J1 will finish on time, J2 will be 3 hours late, and J3 will finish 1 hours late. This means that the weighted tardiness sum is equal to 3×1+1×2=5. 5 Job 1 10 15 Job 3 1 hour late 3 hours late Figure 5.5: Visual representation of the sequence of jobs Job Due Time Completion Time Lateness 20 Job 2 Weighted Tardiness J1 14 11 0 0 J2 20 23 3 3 J3 17 18 1 2 Figure 5.4: Calculating the weighted tardiness The SMWT problem is challenging to solve as its complexity grows exponentially with the number of jobs. Thus making it computationally ●⚫expensive, and often impossible, to find the best possible solution ⚫ ⚫for large input sizes. Optimization algorithms are used to obtain near-optimal solutions for a problem in a reasonable amount of time. وزارة التعليم Ministry of Education 268 2024-1446 23

Job Shop Scheduling (JSS) Problem The Job Shop Scheduling (JSS) problem, is another classic scheduling problem that has been widely studied in the optimization field. The JSS problem involves scheduling a set of jobs on multiple machines, where each job has to be processed in a specific order and time on each machine in relation to the other jobs. Goal To minimize the total completion time (makespan) of all jobs. Variants of the problem Other variants of this problem introduce multiple additional constraints, such as: • Each job has a "release" date before which it cannot be started, in addition to a deadline date. • Some jobs have to be scheduled before others due to precedence constraints between them. • Each machine has to undergo periodic maintenance according to a strict maintaince schedule. Machines cannot service jobs during maintenance and a job cannot stop once it has started. Each machine needs to have some downtime after completing a job. The length of the downtime might be fixed or it may vary across machines. It might also depend on the time that it took to complete the previous job. The above are only a subset of the various complex constraints and problem variants that occur in real-world scheduling problems. Each variant has its own unique characteristics and practical applications, and different optimization algorithms may be more suitable for solving each variant. Using Python and Optimization to Solve the SMWT Problem The following code can be used to create randomized instances of the SMWT problem: import random # creates an instance of the Single-Machine Weighted Tardiness problem def create_problem_instance(job_num, # number of jobs to create duration_range, # job duration range deadline_range, #deadline range weight_range): # importance weight range # generates a random duration, deadline, and weight for each job durations = [random.randint(*duration_range) for i in range(job_num)] deadlines = [random.randint(*deadline_range) for i in range(job_num)] weights = [random.randint(*weight_range) for i in range(job_num)] # returns the problem instance as a dictionary return {'durations':durations, 'deadlines': deadlines, 'weights': weights} وزارة التعليم Ministry of Education 2024-1446 269

The random.randint(x,y) function is used to generate a random integer between x and y. A different way to use this function is to provide a list (x,y] or a tuple (x,y). In that case, the * symbol needs to be typed before the list, exactly as seen in the function above. For example: for i in range(5): # prints 5 random integers between 1 and 10 print(random.randint(*[1, 10])) 65 6 5 5 10 1 The following code uses the create_problem_instance() function to generate a sample problem instance such that: • The instance includes 10 jobs. • Each job can last between 5 and 20 time units. We will assume hours as time units for the remainder of this lesson. • Each job has a deadline that can range between 5 and 50 hours. The deadline clock starts from the moment the first job starts using the machine. For example, if the deadline for a job is equal to 10, then this means that the job has to be completed within 10 hours from the beginning of the job that was scheduled first. • The weight of each job is an integer between 1 and 3. number of jobs to create job duration range create_problem_instance(10, [5,20], [5, 50], [1, 3]) {'durations' [18, 17, 17, 6, 9, 6, 20, 12, 9, 19], [39, 31, 6, 42, 48, 10, 39, 16, 34, 35], 'weights' [2, 2, 3, 2, 1, 3, 2, 1, 3, 1]} 'deadlines' deadline range importance weight range The following function can be used to evaluate the quality of a schedule that has been produced by any algorithm for a specific problem instance. The function accepts a problem instance and a schedule. It then goes over all the jobs in their scheduled order to compute their finish times, as well as the total weighted tardiness of the entire schedule. The latter is computed by computing the tardiness of each job (with respect to its deadline), multiplying it by the job's weight, and adding the result to the sum. # computes the total weighted tardiness of a given schedule for a given problem instance def compute_schedule_tardiness (problem, schedule): #gets the information for this problem durations, weights, deadlines-problem['durations'], problem['weights'], problem['deadlines'] job_num = len(schedule) # gets the number of jobs finish_times = [0] * job_num #stores the finish time for each job schedule_tardiness = 0 # initializes the weighted tardiness of the overall schedule to 0 وزارة التعليم Ministry of Education 270 2024-1446

for pos in range(job_num): # goes over the jobs in scheduled order job_id=schedule[pos] # schedule[pos] is the id in the 'pos' position of the schedule if pos == 0: # if this is the job that was scheduled first (position 0) # the finish time of the job that starts first is equal to its run time finish_times[pos] = durations[job_id] else: # for all jobs except the one that was scheduled first # the finish time is equal to the finish time of the previous time plus the job's run time finish_times[pos] = finish_times[pos-1] + durations[job_id] # computes the weighted tardiness of this job and adds it to the schedule's overall tardiness schedule tardiness += weights [job_id] * max(finish_times[pos] deadlines[job_id], ☺) return schedule_tardiness, finish_times - The compute_schedule_tardiness() function will be used to evaluate schedules and will serve as a useful tool for all the algorithms that will be presented in this lesson for the solution of the SMWT problem. fx Itertools.Permutations() Function The brute-force solver will use the itertools.permutations() function to create all possible schedules (job combinations). It will then compute the tardiness of each possible schedule and report the best one (the one with the lowest total tardiness). The itertools.permutations() function accepts a single iterable (e.g. list) and creates each possible permutation of input values. The following simple example demonstrates the use of the permutations() function and shows the permutations of all given job ids: job_ids [0,1,2] # the ids of 3 jobs = for schedule in itertools.permutations(job_ids): print(schedule) (0, 1, 2) (0, 2, 1) (1, 0, 2) (1, 2, 0) (2, 0, 1) (2, 1, 0) Brute-force solvers are better used for small problems. An instance of the SMWT problem with N jobs has N! possible schedules. For N = 5, this creates only 5! = 120 schedules. However, the number skyrockets for N = 10 to 10! = 3,628,800 and for N = 11 to 11! 39,916,800. Brute-Force Solver In the previous lesson, you learnt how to implement a brute-force solver for the team formation problem. Even though the solver was shown to be too slow for larger problems, its ability to always find the optimal (best possible) solution for small instances was useful for evaluating the quality of the solutions produced by faster optimization algorithms that do not guarantee optimality. Similarly, pill the following brute-force solver can be used to solve an instance of the SMWT problem. Ministry of Education 2024-1446 271

import itertools def brute force_solver (problem): # gets the information for this problem durations, weights, deadlines-problem['durations'], problem['weights'], problem['deadlines'] job_num = len(durations) # number of jobs # Generates all possible schedules all_schedules = itertools.permutations (range(job_num)) # Initializes the best solution and its total weighted tardiness best_schedule = None #initialized to None # 'inf' stands for 'infnity'. Python will evaluate all numbers as smaller than this value. best tardiness = float('inf') #stores the finish time of each job in the best schedule best_finish_times = None #initalized to None for schedule in all_schedules: # for every possible schedule # evalutes the schedule tardiness, finish_times-compute_schedule_tardiness (problem, schedule) if tardiness < best_tardiness: # this schedule is better than the best so far best_tardiness = tardiness best_schedule = schedule best_finish_times = finish_times # returns the results as a dictionary return {'schedule': best_schedule, 'tardiness': best_tardiness, 'finish_times':best_finish_times} The solver returns the best schedule, its tardiness, and the finish time of each job given this best schedule. For example, if a 3-job schedule has finish times equal to [10, 14, 20], then this means that the job that started first finished after 10 hours, The second job finished 4 hours after that, and the last job finished 6 hours after the second job was completed. number of jobs to create deadline range sample_problem = create_problem_instance(5, [5, 20], [5, 30], [1, 3]). brute force_solver(sample_problem) job duration importance {'schedule': (0, 2, 1, 3, 4), range weight range 'tardiness': 164, 'finish_times': [5, 11, 21, 36, 51]} وزارة التعليم Ministry of Education 272 2024-1446

Greedy Heuristic Solver This greedy solver uses a simple heuristic to sort the jobs and decide the order in which they should be scheduled. It then goes over the jobs in this order to compute the finish time of each job and the total weighted tardiness of the entire schedule. For this particular example, the greedy solver returns exactly the same type of output as the brute-force solver. The greedy solver accepts two parameters: the problem to be solved and the heuristic function (job- sorting criterion) to be used. This allows the user to implement any heuristic function of their choosing as a Python function and pass it to the greedy solver as a parameter. The following function implements an optimization algorithm that uses a greedy heuristic function to solve the problem: def greedy_solver (problem, heuristic): #gets the information for this problem durations, weights, deadlines = problem['durations'], problem['weights'], problem['deadlines'] job_num = len(durations)# gets the number of jobs # creates a list of job indices sorted by their deadline in non-decreasing order schedule sorted(range(job_num), key = = lambda j: heuristic(j, problem)) # evaluates the schedule tardiness, finish_times = compute_schedule_tardiness (problem, schedule) # returns the results as a dictionary return {'schedule': schedule, 'tardiness': tardiness, 'finish_times': finish_times} In this example, the greedy heuristic function used to select the next job to be scheduled chooses the job having the closest deadline. The 'lambda' syntax is used with Python's sorted() function when the goal is to sort a list of elements based on a value that is computed separately for each element. The following function returns the deadline of a specific job in a given problem instance: # returns the deadline of a given job def deadline_heuristic (job, problem): # accesses the deadlines for this problem and returns the deadline for the job return problem ['deadlines'][job] Passing this deadline_heuristic() function as a parameter to the greedy solver means that the solver will schedule (sort) the jobs in ascending deadline order. This means that the jobs with the earliest pull deadlines will be scheduled first. Ministry of Education 2024-1446 273

greedy_sol = greedy_sol greedy_solver(sample_problem, deadline_heuristic) {'schedule': [3, 1, 4, 0, 2], 'tardiness': 124, 'finish_times': [15, 26, 32, 48, 57]} The following function implements an alternative heuristic that also takes into account the weights of the jobs when deciding their order in the schedule: # returns the weighted deadline of a given job def weighted_deadline_heuristic (job, problem): # accesses the deadlines for this problem and returns the deadline for the job return problem [ 'deadlines'][job] / problem['weights'][job] weighted_greedy_sol=greedy_solver(sample_problem, weighted_deadline_heuristic) weighted_greedy_sol {'schedule': [3, 2, 1, 4, 0], 'tardiness': 89, 'finish_times': [15, 24, 35, 41, 57]} Local Search Local Search Local search is a heuristic optimization method that focuses on exploring the neighborhood of a given solution to improve it. Even though the greedy solver is much faster than the brute-force approach, it also tends to produce lower quality solutions with a significantly higher tardiness. A way to improve a solution computed by a greedy algorithm or by any other approach is Local Search. In Local Search, a starting solution is iteratively refined by examining its neighboring solutions, which are obtained by applying small modifications to the current solution. For many optimization problems, a common approach for modifying a solution is by iteratively swapping elements. For instance, in the team-formation problem that was covered in the previous lesson, a local search approach would try to create a better team by swapping team members with workers who are currently not a part of the team. The greedy heuristic solver constructed the solution step-by-step until eventually a complete and final solution was obtained. On the contrary, local search methods start with a complete solution (that may be of moderate or even bad quality), and work iteratively to improve the quality of the solution. Each step, a small change is made to the current solution, and the quality of the resulting solution (known as the neighbor) is evaluated. If the neighbor solution has better quality, then it replaces the current solution, and the search continues. Otherwise, the neighbor solution is discarded and the process is repeated to generate another neighbor. The search terminates when no neighbor solution can be found having quality better than the current solution. The best solution found is returned. وزارة التعليم Ministry of Education 274 2024-1446

Local_search_solver() Function The following local_search_solver() function implements a swap-based local search solver for the SMWT problem. The function accepts four parameters: • A problem instance. • A greedy heuristic that will be used by the greedy_solver() function to compute an initial solution. A swap_selector function that will be used to select two jobs that will swap their positions in their schedule. For example, if the current solution of a 4-job problem is [0,2,3,1], and the swap selector decided to swap the first and last jobs, the new candidate solution would be [1,2,3,0]. • A max_iterations integer that determines how many swaps should be attempted before the solver returns the best solution found so far. In each iteration, the solver selects two jobs to swap. It then creates a new schedule that swaps the two jobs but is otherwise identical to the original. If the new schedule has a lower weighted tardiness than best schedule found so far, then it replaces it. The solver has the exact same output as the greedy and brute-force solvers. The behavior of local search optimization algorithms is heavily influenced by the strategy that is used to iteratively modify the solution. def local_search_solver(problem, greedy_heuristic, swap_selector, max_ iterations): # gets the information for this problem durations, weights, deadlines=problem['durations'], problem['weights'], problem deadlines'] job_num = len(durations) # gets the number of jobs # uses the greedy solver to get a first schedule # this schedule will then be iteratively refined through local search greedy_sol = greedy_solver (problem, greedy_heuristic) # the best schedule so far best_schedule, best_tardiness, best_finish_times = greedy_sol['schedule'], greedy_sol['tardiness'], greedy_sol['finish_times'] # local search for i in range(max_iterations): # for each of the given iterations #chooses which two positions to swap pos1, pos2 = swap_selector(best_schedule) new_schedule = best_schedule.copy() # create a copy of the schedule #swaps jobs at positions pos1 and pos2 new_schedule[pos1], new_schedule[pos2] = best_schedule[pos2], best_schedule[pos1] وزارة التعليم Ministry of Education 2024-1446 275

# computes the new tardiness after the swap new_tardiness, new_finish_times = compute_schedule_tardiness (problem, new_schedule) # if the new schedule is better than the best one so far if new_tardiness < best_tardiness: # the new_schedule becomes the best one best_schedule = new_schedule best tardiness = new_tardiness best_finish_times = new_finish_times # returns the best solution return {'schedule': best_schedule, 'tardiness': best_tardiness, 'finish_times': best_finish_times} The neighbors of a solution in this example are all solutions that are obtained by selecting two jobs within the solution and swapping their positions in their schedule. The following function implements a random swap by simply selecting two random jobs in the given schedule that should exchange places. def random_swap(schedule): job_num = len(schedule) # gets the number of scheduled jobs pos1 = random.randint(0, job_num - 1) # samples a random position pos2 = pos1 while pos2 == pos1: #keeps sampling until it finds a position other than pos1 pos2 = random.randint(0, job_num - 1) # samples another random position return pos1, pos2 # returns the two positions that should be swapped The following function then adopts a different strategy by always choosing to swap a random pair of jobs that are adjacent in the schedule. For example, if the current schedule for a 4-job problem instance was [0,3,1,2], then the only candidate swaps would be 0<>3, 3<>1, and 1<>2. def adjacent_swap(schedule): one) job_num = len(schedule) # gets the number of scheduled jobs pos1 = random.randint(0, job_num - 2) #samples a random position (excluding the last pos2 pos1 + 1 # gets the position after the sampled one return pos1, pos2 # returns the two positions that should be swapped وزارة التعليم Ministry of Education 276 2024-1446

The following code uses both swap strategies with the local search solver to solve the sample problem generated in the beginning of this lesson. print(local_search_solver(sample_problem, weighted_deadline_heuristic, random_ swap, 1000)) print(local_search_solver(sample_problem, weighted_deadline_heuristic, adjacent_swap, 1000)) {'schedule' [3, 4, 2, 1, 0], 'tardiness': 83, 'finish_times': [15, 21, 30, 41, 57]} {'schedule': [3, 4, 2, 1, 0], 'tardiness': 83, 'finish_times': [15, 21, 30, 41, 57]} The results show the best schedule [3, 4, 2, 1, 0] for this example and also the overall tardiness (83) and finish times (job 3 will finish on the 15th unit of time, job 4 on the 21st and so on). Comparing Solvers The following code uses the create_problem_instance() function to generate two datasets: • A dataset of 100 SMWT problem instances with 7 jobs each. • A dataset of 100 SMWT problem instances with 30 jobs each. The first dataset will be used to compare the performance of all solvers that were described in this lesson: 1. The brute-force solver. 2. The greedy solver with the deadline heuristic. 3. The greedy solver with the weighted deadline heuristic. 4. The local search solver with random swaps and a greedy solver with the deadline heuristic to find the initial solution. 5. The local search solver with random swaps and a greedy solver with the weighted deadline heuristic. 6. The local search solver with adjacent swaps and a greedy solver with the deadline heuristic. 7. The local search solver with adjacent swaps and a greedy solver with the weighted deadline heuristic. The second dataset will be used to compare all solvers except for the brute-force one, which is far too slow for 30-job problems. #Dataset 1 problems 7 = [] for i in range(100): problems_7.append(create_problem_instance(7, [5, 20], [5, 50], [1, 3])) #Dataset 2 problems 30 = [ ] for i in range(100): problems_30.append(create_problem_instance(30, [5,20], [5, 50], [1, 3])) وزارة التعليم Ministry of Education 2024-1446 277

Compare() Function The following compare() function uses all the solvers to solve all problems in the given dataset. It then returns the average tardiness value achieved by each solver over all the problems in the dataset. The function also accepts a boolean use_brute parameter to determine if the brute-force solver should be used or not. from collections import defaultdict import numpy def compare(problems, use_brute): # comparison on Dataset 1 # maps each solver to a list of all tardiness values it achieves for the problems in the given dataset results = defaultdict(list) for problem in problems: # for each problem in this datset # uses each of the solvers on this problem if use_brute == True: results['brute-force'].append(brute_force_solver (problem) ['tardiness']) results['greedy-deadline'].append(greedy_solver (problem, deadline_ heuristic) ['tardiness']) results['greedy-weighted_deadline'].append(greedy_ solver(problem, weighted_deadline_heuristic) ['tardiness']) results['ls-random-wdeadline'].append(local_search_solver (problem, weighted_deadline_heuristic, random_swap, 1000) ['tardiness']) results['ls-random-deadline'].append(local_search_solver (problem, deadline heuristic, random_swap, 1000) ['tardiness']) results['ls-adjacent-wdeadline'].append(local_search_solver(problem, weighted_deadline_heuristic, adjacent_swap, 1000)['tardiness']) results['ls-adjacent-deadline'].append(local_search_solver(problem, deadline heuristic, adjacent_swap, 1000) ['tardiness']) for solver in results: # for each solver # prints the solver's mean tardiness values print(solver, numpy.mean(results [solver])) The compare() function can now be used with both the problems_7 and problems_30 datasets: compare(problems 7, True) brute-force 211.49 greedy-deadline 308.14 greedy-weighted_deadline 255.61 ls-random-wdeadline 212.35 ls-random-deadline 212.43 ls-adjacent-wdeadline 220.62 ls-adjacent-deadline 224.36 compare(problems_30, False) greedy-deadline 10126.18 greedy-weighted_deadline 8527.61 وزارة التعليم Ministry of Education 278 2024-1446 ls-random-wdeadline 6647.73 ls-random-deadline 6650.99 ls-adjacent-wdeadline 6666.47 ls-adjacent-deadline 6664.67

Exercises 1 Describe two different strategies (swapping, inversion, shifting etc.) for the local search approach to solving the SMWT problem. 2 How many possible schedules (solutions) are there for an instance of the SMWT problem with 9 jobs? وزارة التعليم Ministry of Education 2024-1446 279

3 You want to create a brute-force solver for the SMWT problem. Complete the following code so that the function utilizes brute force to find the optimal scheduling permutation. def brute force_solver (problem): # gets the information for this problem durations, weights, deadlines-problem['durations'], problem['weights'], problem['deadlines'] job_num = len( # generates all possible schedules ) # number of jobs وزارة التعليم Ministry of Education 280 2024-1446 all_schedules = itertools. (range(job_num)) # initializes the best solution and its total weighted tardiness best_schedule = # initialized to None # 'inf' stands for 'infinity'. Python will evaluate all numbers as smaller than this value best tardiness = float(' #stores the finish time of each job in the best schedule best_finish_times= #initalized to None for schedule in all_schedules: # for every possible schedule # evalute the schedule tardiness, finish_times=compute_schedule_tardiness(problem, schedule) if tardiness<best_tardiness: # this schedule is better than the best so far best_tardiness= best_schedule= best_finish_times= # return the results as a dictionary return {'schedule': best_schedule, 'tardiness': best_tardiness, 'finish_times': best_finish_times}

4 You want to create a local search solver for the SMWT problem. Complete the following code so that the function utilizes local search to find the optimal scheduling permutation. def local_search_solver(problem, greedy_heuristic, swap_selector, max_ iterations): # gets the information for this problem durations, weights, deadlines-problem['durations'], problem['weights'], problem['deadlines'] job_num = len( )# gets the number of jobs # uses the greedy solver to get a first schedule # this schedule will be then iteratively refined through local search greedy_sol (problem, greedy_heuristic) #remembers the best schedule so far best_schedule, best_tardiness, best_finish_times=greedy_ sol['schedule'], greedy_sol['tardiness'],greedy_sol['finish_times'] # local search for i in range( ): # for each of the given iterations # chooses which two positions to swap pos1, pos2= (best_schedule) new_schedule = best_schedule. () # creates a copy of the schedule #swaps jobs at positions pos1 and pos2 schedule [pos1] new_schedule [pos1], new_schedule [pos2] = best_schedule[pos2], best_ # computes the new tardiness after the swap new_tardiness, new_finish_times = compute_schedule_tardiness(problem, new_schedule) # if the new schedule is better than the best one so far if new_tardiness < best_tardiness: # the new_schedule becomes the best one best_schedule = وزارة التعليم Ministry of Education 2024-1446 best_tardiness = best_finish_times= # returns the best solution return {'schedule': best_schedule, 'tardiness': best_tardiness, 'finish_times': best_finish_times} 281

5 Describe how local search works. 6 Write your observations about the results of the the greedy solvers compared to the local search solvers in the 30 job problem. Why do you think in the 30 job problem the brute-force solver was not used? وزارة التعليم Ministry of Education 282 2024-1446