7.2: Primeros pasos
- Page ID
- 110821
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
Para comenzar a pensar en la programación, consideremos un taller de autos que está convirtiendo un automóvil de gas a eléctrico. Se trata de una serie de pasos. Se da una estimación de tiempo para cada tarea.
Tarea 1: Retirar piezas de motor y gas (2 días)
Tarea 2: Limpiar con vapor el interior del automóvil (0.5 días)
Tarea 3: Comprar un motor eléctrico y controlador de velocidad (2 días para viajar)
Tarea 4: Construir la parte que conecta el motor a la transmisión del automóvil (1 día)
Tarea 5: Construir racks de baterías (2 días)
Tarea 6: Instalar el motor (0.5 días)
Tarea 7: Instalar el controlador de velocidad (0.5 días)
Tarea 8: Instalar los racks de baterías (0.5 días)
Tarea 9: Cablear la electricidad (1 día)
Algunas tareas tienen que ser completadas antes que otras — ¡ciertamente no podemos instalar el nuevo motor antes de retirar el motor viejo! Hay algunas tareas, sin embargo, que pueden ser trabajadas simultáneamente por dos personas diferentes, como construir los racks de baterías e instalar el motor.
Para ayudarnos a visualizar el orden de las tareas, crearemos un dígrafo.
Un diagraph es una representación gráfica de un conjunto de tareas en las que las tareas se representan con puntos, llamados vértices, y las flechas entre vértices se utilizan para mostrar el orden.
Por ejemplo, esta dígrafa muestra que la Tarea 1, anotada\(T_1\) para compacidad, necesita ser completada antes de la Tarea 2. El número entre paréntesis después del nombre de la tarea es el tiempo requerido para la tarea.
Un dígrafo completo para nuestra conversión de autos se vería así:
El tiempo que lleve completar este trabajo dependerá en parte de cuántas personas estén trabajando en el proyecto.
En la jerga de programación, los trabajadores que completan las tareas se denominan procesadores. Si bien en este ejemplo los procesadores son humanos, en algunas situaciones los procesadores son computadoras, robots u otras máquinas.
Por simplicidad, vamos a hacer las suposiciones muy grandes de que cada procesador puede hacer cada tarea, que todos tomarían el mismo tiempo para completarla, y que solo un procesador puede trabajar en una tarea a la vez.
El tiempo de finalización es el tiempo que tardará en completar todas las tareas. El tiempo de finalización dependerá del número de procesadores y del horario específico.
Si solo tuviéramos un procesador trabajando en esta tarea, es fácil determinar el tiempo de finalización; solo sumar los tiempos individuales. Asumimos que una persona no puede trabajar en dos tareas al mismo tiempo, ignorar cosas como los tiempos de secado durante los cuales alguien podría trabajar en otra tarea. Programando con un procesador, un posible horario se vería así, con un tiempo de finalización de 10 días.
En este horario, se cumplen todos los requisitos de pedido. Este ciertamente no es el único horario posible para un procesador, pero ningún otro horario podría completar el trabajo en menos tiempo. Debido a esto, este es un horario óptimo con un tiempo de acabado óptimo — no hay nada mejor.
Un horario óptimo es el horario con el menor tiempo de finalización posible.
Para dos procesadores, las cosas se vuelven más interesantes. Para pequeños dígrafos como este, probablemente podríamos jugar y conjeturar y verificar un horario bastante bueno. Aquí habría una posibilidad:
Con dos procesadores, el tiempo de acabado se redujo a 5.5 días. ¿Qué hacía el procesador 2 durante el último día? Nada, porque no había tareas para que el procesador hiciera. Esto se llama tiempo de inactividad.
El tiempo de inactividad es el tiempo en el horario cuando no hay tareas disponibles para que el procesador funcione, por lo que se sientan inactivos.
¿Este horario es óptimo? ¿Podría haberse terminado en 5 días? Debido a que todas las demás tareas tenían que completarse antes de que la tarea 9 pudiera comenzar, no habría forma de que ambos procesadores pudieran estar ocupados durante la tarea 9, por lo que no es posible crear un horario más corto.
Entonces, ¿cuánto tiempo tomará si usamos tres procesadores? ¿Acerca de\(10/3 = 3.33\) los días? Nuevamente adivinaremos y verificaremos un horario:
Con tres procesadores, el trabajo aún tardaba 4.5 días. Es un poco más difícil decir si este horario es óptimo. Sin embargo, podría ser útil notar que dado que las Tarea 1, 2, 6 y 9 tienen que completarse secuencialmente, no hay forma de que este trabajo pueda completarse en menos de\(2+0.5+0.5+1 = 4\) días, independientemente del número de procesadores. Cuatro días es, para este dígrafo, el tiempo mínimo absoluto para completar el trabajo, llamado el tiempo crítico.
El tiempo crítico es el tiempo mínimo absoluto para completar el trabajo, independientemente del número de procesadores que trabajan en las tareas.
El tiempo crítico se puede determinar observando la secuencia de tareas más larga en el dígrafo, llamada ruta crítica