Operations Management Alberto Santini Instructions Final Project 1 Problem description In a factory assembly line, you are in charge of a machine that has to process a set of jobs J = {1,...,n}. Each job j J has the following characteristics: Processing time. Once started, it takes p; units of time to complete the job. . Release time. The job becomes available for processing at time rj. Therefore, it cannot start before this time. For example, if the input material for the job comes from another part of the factory, r; is the time when the material is available at your machine. Due time. Ideally, each job should be completed by time dj. If the job is completed after this deadline, it is marked as a tardy job. You should avoid having many tardy jobs or the assembly line stops working smoothly. At the same time, it is fine to complete a job before the deadline. You should decide in which order you want to process the jobs, keeping in mind that the machine can only process one job at a time and that, once started, a job cannot be interrupted. Your objective is to minimise the number of tardy jobs. To this end, you devise a mathematical programming formulation using the following variables: . uj = {0, 1} for each job j J. This variable will take the value one if and only if job j is tardy in your schedule. c; 0 for each job j J. This variable will hold the completion time of job j. Yjk {0, 1} for each pair of jobs j, k J with j < k. This variable will take the value one if and only if job j is processed before job k in your schedule. Remark that we only create these variables for j A mixed-integer programme to create a machine schedule is the following: min ; subject to c; rj + Pj - ; Ck +P; Myjk Ckcj+Pk - M(1-jk) cj dj + Muj uj {(0,1) Bjk {0,1} (1a) Vj J (1b) Vj, k J (j < k) (1c) Vj, kJ (j d; and u; = 0 otherwise. 2 Input data format You receive input data from a text file with the following format: = 1 1. The first line contains one integer number, n, representing the number of jobs to schedule. 2. The second line contains n space-separated integer numbers. The j-th such number is the processing time p;. 3. The third line contains n space-separated integer numbers. The j-th such number is the release time rj. 4. The fourth line contains n space-separated integer numbers. The j-th such number is the due time dj. For example, the following is a possible input file with n = 5: 5 8 10 4 6 4 06 12 14 26 40 18 24 24 32 3 Output data format Your programme must write the solution to a file with the following format. The file must contain two lines. The first line will contain a single integer number, the objective value of the optimal solution to the problem. In other words, this is the number of tardy jobs. The second line will contain n space-separated integer numbers. The j-th such number is the completion time of job j in the optimal solution. For example, if you correctly implement the model, the following could be the output file related to the above input: 1 8 18 22 28 32 In this solution, there is only one tardy job. The completion times of the jobs are 8, 18, 22, 28 (tardy), and 32. 4 Practical instructions You will submit exactly one file, and it must be a valid Jupyter Notebook. The filename must be in the form u123456.ipynb where "u123456" is your student ID number, i.e., the number you use to log in to Aula Global. The filename must start with a lowercase letter "u" and end with the .ipynb extension. The student ID is made of the starting lowercase letter "u" and six digits. For example, if your student ID is "u201224", then your notebook will be u201224.ipynb. Examples of invalid notebook filenames are: 201224.ipynb, because there is no starting letter "u". U201224.ipynb, because the letter "U" is uppercase instead of lowercase. u201224.json, because the file extension is not .ipynb. u20122.ipynb, because the letter "u" is followed by five instead of six digits. . submission u201224.ipynb, because the filename contains extra parts. Your notebook will read the input data from a file that follows the specifications explained in Section 2. This file's name will be u123456_input.txt, where "u123456" is your student ID number. This file will be in the same directory as your notebook. After solving the problem, your notebook will write the solution to a file, following the specifica- tions explained in Section 3. The name of the output file must be u123456_output.txt, where "u123456" is your student ID number. The notebook must create this file in the same directory as the notebook itself. For example, if your student ID is "u201224", then your notebook u201224.ipynb will read the data from file u201224_input.txt, and it will write the solution to file u201224_output.txt. When the submission period for the final project is open, I will upload two files, example_input .txt and example_output.txt, that you can use to build confidence in the correctness of your notebook. You shall download the example_input.txt file and rename it to u123456_input.txt (replacing "u123456" with your actual student ID). Then you can run your notebook and pro- duce the corresponding u123456_output.txt file (again, replacing "u123456" with your actual student ID). If your notebook is correct, the contents of the file u123456_output.txt will be identical to those of the file example_output.txt.