Description
1 Introduction
Aviation makes the dream and desire of being able to fly a reality. A strong and affordable global air transport network transcends continents, greatly expands local access to foreign supplies and markets, provides invaluable opportunities for cultural and social exchange, and enhances emergency and humanitarian response capabilities during crises and public health emergencies.
All these opportunities and many more depend on the flawless execution of our flight operations. Air traffic management is a cooperative, international effort and does not stop at borders, on land or in the air. International cooperation of air traffic control providers has helped make commercial aircraft one of the most rapid and dependable mode of travel. Flight operations staff work around the clock to ensure the smooth running of these services. In this project, you will explore these flight operations services’ event-driven flight scheduling and processing routines.
2 Details
In this project you will simulate an air traffic management system. This system has area control centers, air traffic controllers, airports and flights. Area control centers are where flights enter and exit the simulation. Each area control center has a set of airports its’ responsible for and each airport has one air traffic controller. These air traffic controllers are what the area control center will communicate with when processing flight events. Your job is to make sure that each flight is handled correctly.
2.1 ACC • Area control center, or ACC, is the entry and exit point for flights. • Area control centers are identified by a unique code consisting of 4 capital letters. • Each area control center is responsible for a set of airports. Every airport has one and only one air traffic controller. This air traffic controller communicates with the area control center. The area control center will delegate the departure and landing phases of the flight to the air traffic controller. Control will be given back to the area control center when these phases are done.
• There might be more than one area control center. These area control centers are completely independent. They have their own flights, their own airports, and their own air traffic 1 controllers for those airports. In other words, a flight or an airport or an air traffic controller can only be a part of one area control center. • Every airport in an area control center is connected to every other airport in that area control center. • Flights can only fly between airports in the same area control center. Passages between area control centers do not happen.
• Flights need to have some operations done by the area control center to progress forward. At any given time there might be more than one flight that needs their operation done. These flights will form a queue while the area control center is busy. This queue is called the ready queue, because it holds flights that are ready to be processed by the area control center. Area control centers are almost always really busy, but each flight should also have a good response time to ensure the smooth running of flight operations.
To this end, the area control center will process the first flight in the ready queue, however, this flight will only be processed for some predetermined time-slice. If the operations do not finish in the given time-slice, the flight is sent all the way to the back of the queue for further processing; else, if the operations finish the flight continues on with its’ next step. There might be cases where two flights want to enter the ready queue at the same time.
In such a case, if one of the flights is new to the queue and the other one just finished processing and got sent to the back of the queue, the new one has priority. If the both flights are new, then the flight with the lower flight code, by string comparison, has higher priority. Area control centers in this air traffic management system use a time-slice of 30 units of time. The chart below visualizes this time-slice processing regime. Flight entries are flight codes followed by the amount of time needed to finish that flight. 0 F1: 40t F2: 20t F3: 30t F1 F2 F1 F3 . . . 30t 50t 60t 90t time t Flight entry
2.2 ATC • Air traffic control, or ATC, is an auxiliary flight manager. • Each air traffic control is responsible for a single airport. • Flights taking off from or landing at an airport need their operations done by the air traffic controller for that airport. So, when time comes, the area control center will delegate flights to the required air traffic controller. When the take off or land operations end, the air traffic controller will control of the pass the flight back to the area control center.
• At any given time air traffic control might have more than one flight that needs their operation done, just like the area control center. These flights will again form a queue called the ready queue. Air traffic controllers are also very busy, however, unlike the area control center, air traffic control must commit to one flight when it starts processing it. So the first flight in the queue will be processed first, and it will be processed until the completion of its’ operations.
• Air traffic controllers are identified by a unique code consisting of 7 characters, the first 4 characters of which is the area control center code it belongs to, the following 3 characters 2 are numbers from 0 to 999, filled with zeros from the front. These numbers are obtained by placing the airport code of this air traffic control into an available slot in a table of size 1000. Every area control center will have its’ own table, filled with airports it is responsible for. For every ith character of the airport code string, i starting from zero of course, the ASCII value for that character will be multiplied by 31i . These i multiplications will be summed together to generate the initial slot value.
Search for an available slot will start from the position denoted by the last three digits of the initial slot value. If a slot is not available, the next slot will be considered. If the end of the table is reached jump back to the beginning slot of the table and continue. There will not be more than 1000 airports in one area control center, and consequently in one table, so every airport will eventually find a slot. Air traffic control codes are generated in the order their respective airport code appears in the input.
2.3 Flight • Flights are the entities that needs processing. • Each flight has a departure and landing airport, both airports belong to the same area control center. Which area control center these airports belong to will be given in the input. • A flight has 21 operation steps to complete before termination. These steps and their order are explained in detail in the next section. Durations of these steps will be given in the input. • Flights enter and exit the simulation through the area control center. In the area control center flights process their operation steps until termination.
These processing steps repeat a certain form. This form can be visualized as a collection of states the flight can be in. A state diagram is given below to help you visualize the situation. • During processing the flight event will cycle through the states. Twice during these cycles, the flight will exit states that belong to the area control center and enter states that belong to an air traffic control, where it will process either the departure or the landing operation steps of the flight.
After the air traffic control has cycled through its’ states, the flight will be back in the area control center states, and it will continue processing from there. ACC ATC New Terminated Running 1 Waiting 1 Ready 1 Ready 2 Waiting 2 Running 2 admitted exit time-slice expired process operations wait completion wait event landing/departure event landing/departure completion wait event process operations wait completion 3
2.4 Operation Times Every flight will follow a certain chain of states. Each state needs some amount of time to complete its’ operation. These state chains are given below, in order. Operation times will be given for each running and waiting state in the input. The completion of running states depend on the availability of either the area control center or the air traffic control responsible for the execution. So, time spent in the ready states depends on the scheduling situation.
Waiting states just require the flight to wait for a certain amount of time before continuing with the next operation. ACC – Running: ACC initial processing. ACC – Waiting: Relaying flight information to ACC. ACC – Running: Control transfer from ACC to departure ATC. ATC Departure – Running: Departure ATC initial processing. ATC Departure – Waiting: Boarding wait. ATC Departure – Running: Taxi information processing. ATC Departure – Waiting: Taxi wait. ATC Departure – Running: Takeoff clearance processing. ATC Departure – Waiting: Takeoff wait. ATC Departure – Running: Control transfer from departure ATC to ACC. ACC – Running: Flight path processing. ACC – Waiting: Flight wait. ACC – Running: Control transfer from ACC to arrival ATC. ATC Arrival – Running: ATC initial processing and landing clearance processing. ATC Arrival – Waiting: Landing wait. ATC Arrival – Running: Taxi information processing. ATC Arrival – Waiting: Taxi wait. ATC Arrival – Running: Gate and ground crew information processing. ATC Arrival – Waiting: Disembarkation wait. ATC Arrival – Running: Control transfer from arrival ATC to ACC. ACC – Running: ACC wrap-up.
3 Input & Output
3.1 Input Input file path will be given as the first program argument. Format Input begins with a single line containing two space-separated integers A and F. Then, A lines follow, the ith of which contains space-separated codes starting with Ai the ACC code, followed by airport codes connected to that ACC, jth of which is Hij .
Then, F lines follow, the kth of which contains 26 space-separated values, Tk admission time, Fk the flight code, Ak ACC code, Ok departure airport code, Dk arrival airport code, respectively. Followed by 21 space-separated integers, denoting the operation times for the flight Fk, mth of these operation times is Pkm. 4 Constraints 1 ≤ A, i ≤ 104 1 ≤ F, k ≤ 6 · 106 0 ≤ Tk ≤ 109 2 ≤ j ≤ 1000 1 ≤ m ≤ 21 1 ≤ Pkm ≤ 500 Ai , Ak ∈ [“AAAA”-“ZZZZ”] Ok, Dk, Hij ∈ [“AAA”-“ZZZ”] Fk ∈ [“AA1111”-“ZZ9999”] 3.2 Output Output file path will be given as the second program argument.
Format The output will consist of A lines, one for each ACC. Ordering between ACC lines does not matter. Each ACC line has an ACC code followed by a space-separated integer denoting the time of termination of the last flight. The next j space-separated strings are airport codes and their slot concatenated together. These values are for each ACC.
4 Submission
Your project will be graded automatically. So it’s important that you carefully follow the submission instructions. First, all of your source files, and nothing more, should be collected under Project3/src. Then, you should zip the Project3 folder and rename it to p3_.zip (e.g., p3_2020400999.zip). This zip file will be submitted through moodle. These steps should be followed in order. Your program must be runnable through the terminal. We will compile your code with the javac command. The target version is 17.
Hence, it is imperative that your project structure is correct, otherwise you will not be able to get any points from the automatic grading system. The compiled program will be run using java command. Your program should be able to run with full-path arguments.
5 Grading Grading of this project is based on the automatic compilation and run and the success of your code in test cases. If your code compiles and runs with no error, then you will get 10% of the project grade. 90% of your grade will be the sum of points collected from each input/output test case. Each test case will have equal weight. Outputs will have partial grading, each correct ACC line will contribute towards your final grade. Wrong values do not reduce your grade. Maximum project grade is 100%.
6 Warnings • This is an individual project. • All source codes are checked automatically for similarity with other submissions and exercises from previous years. Make sure you write and submit your own code. Any sign of cheating will be penalized by at least -50 points at first attempt and F grade in case of recurrence. 5 • Make sure you document your code with necessary inline comments and use meaningful variable names. Do not over-comment, or make your variable names unnecessarily long. This is very important for partial grading.
• Do not start coding right away. Think about the structure of your program and the possible complications resulting from it before coding. • Make sure that the white-spaces in your output is correct. You can disregard the ones at the end of the line.
• Questions about the project should be sent through the contact address in the first page. • There will be a time limit of 60 seconds for your program execution. This is not a strict time limit, execution times may vary for each run, thus objections regarding to time limits will considered if necessary. 6