3 de mayo de 2016

Secuenciación con una máquina: 2 teoremas

Haciendo uso del razonamiento de 4 partes mencionado cerca del final del post anterior, demostraremos 2 teoremas que nos ayudarán a reducir el número de suposiciones que hicimos en el mismo, pues resulta que algunos de ellos son consecuencia de otros.

Teorema 2.1

Dado el problema de programación de una sola máquina con una medida de desempeño regular, los programas sin tiempos muertos insertados constituyen un conjunto dominante.

Demostración

Sea $S$ un programa que contiene tiempos muertos insertados. En particular, suponga que en S, la máquina está en desuso en un intervalo $(a, b)$.
Sea S' un programa idéntico a S hasta el instante a, y en el cual los trabajos que ocurren en S después del instante b están recorridos una tiempo $b-a \gt 0$. Entonces cualquier trabajo j para el cual $C_j \leq a$ en el programa $S$ tendrá $C'_j = C_j$ en $S'$. Por otro lado, para cualquier trabajo j tal que $C_j \gt a$ en S, se tiene que $C'_j = C_j -(b-a)$ en S'. Por lo tanto, $C'_j \leq C_j \forall j$
Se sigue que $Z' \leq Z$ para cualquier medida regular, de tal manera que remover tiempos muertos nunca puede resultar en peor desempeño. Por lo que los programas sin tiempos muertos insertados constituyen un conjunto dominante.

De manera similar, es posible mostrar que en este problema, el conjunto de programas de permutación sin interrupciones es un conjunto dominante para cualquier medida regular.
En otras palabras, la condición C7 puede ser relajada, permitiendo interrumpir las operaciones, pero las interrupciones jamás derivarán en un programa  con mejor desempeño. Lo anterior resulta en el segundo teorema:

Teorema 2.2

En el problema de una máquina con medida regular, los programas sin interrupciones constituyen un conjunto dominante.

Como consecuencia de estos dos teoremas se sigue que las condiciones C6 y C7 no se necesitan explícitamente para los problemas de una máquina con medida regular, porque ya caracterizan conjuntos dominantes con las suposiciones C1 a C5.

Resumen

Los teoremas que aquí hemos mencionado nos permiten relajar las suposiciones que hicimos anteriormente, pues 2 de ellas caracterizaban conjuntos dominantes que ya están contenidas en las suposiciones C1 a C5.

27 de abril de 2016

Creando un bot con node y twit: parte 1

Una vez instalado node es bastante sencillo de empezar a crear un bot. Pero primero necesitamos tener una cuenta de twitter, una vez que tengamos una debemos dirigirnos a https://apps.twitter.com/

Aquí creamos las apps
Una vez allí, creamos una nueva app, y nos encontraremos con lo siguiente:

Configuración inicial de la app
Para nuestros fines utilicé como website http://127.0.0.1.
Ahora leemos y aceptamos el acuerdo de desarrollador

Developer agreement
En la sección de "key and access tokens" copiamos el consumer key y el consumer secret.


Generamos el access token




Y lo copiamos



Pasaremos a node, y a instalar el paquete twit que usaremos para nuestro bot. Ahora puedes crear una carpeta para hacer el proyecto, o bien, instalar twit globalmente, pero yo recomiendo lo primero. Para instalar twit corremos el siguiente comando:

npm install twit

O si nos decidimos a instalarlo globalmente:

npm install -g twit 
Creamos un archivo js, yo lo llamé twitterBot.js, y aquí está el código:



Twit funciona como una interfaz a la API REST de twitter, el proceso para empezar a utilizarlo una vez cargado consiste en:

  1. Instanciar Twit, pasando los 4 tokens de autentificación. (En este caso la llamé Bot)
  2. Llamar al método que deseemos de esa instancia. Los métodos son verbos (como post, get, postMediaChunked, etc.) o bien, el sustantivo streeam si se trata de la API STREAM
  3. Pasar al menos 2 parámetros a la función anterior:
    1. Ruta o endpoint. Ejemplo: 'statuses/update'. (estos se especifícan aquí)
    2. [meta]Parámetros de configuración, regularmente en forma de un objeto. Ejemplo: {status: "este es un ejemplo"}. Las opciones disponibles para estos parámetros se especifícan en la documentación de cada endpoint (aquí por ejemplo).
    3. Una función callback para procesar los resultados del request al terminar.

27 de marzo de 2016

Secuenciación con una máquina

Nota:
Después de pensarlo un rato, he decidido cambiar "schedule" por "programa" y "scheduling" por "programación", pues me parece un lenguaje más natural al leer. El uso de la palabra "programa" quedará claro por el contexto, y generalmente se referirá a lo que me refería con schedule, salvo que indique lo contrario.

El problema de secuenciación pura (PSP, por "pure sequencing problem") es un problema de programación especializado en el que un ordenamiento de trabajos determina completamente el programa.

El PSP más simple es el que consiste de un solo recurso o una sola máquina, y cuyos elementos a procesar son deterministas.

Una idea clave aquí, es notar que el descomponer y simplificar sistemas y problemas es fundamental para entenderlos, y una excelente manera de empezar a modelarlas.

Además de limitar el problema a una sola máquina, se puede caracterizar el problema fundamental limitándonos a las siguientes condiciones:

C1. Hay n trabajos de una operación simultáneamente disponibles para procesarse (en t = 0).
C2. Las máquinas pueden procesar a lo más un trabajo a la vez.
C3. Los tiempos de instalación son independientes del orden de los trabajos.
C4. Los descriptores de trabajo son deterministas y se conocen con antelación.
C5. Las máquinas están disponibles de manera continua (y sin descomposturas/bajas).
C6. Las máquinas no se mantienen desocupadas cuando hay trabajo pendiente. 
C7. Una vez iniciada una operación, esta continúa sin interrupción
Dadas estas condiciones, se tiene una correspondencia uno a uno entre una secuencia de n trabajos y una permutación de los índices de los trabajos $1, 2, …, n$. Es decir que el número de soluciones distintas del problema es $n!$ (el número total de permutaciones de n elementos). Siempre que un programa puede ser caracterizado por una permutación de enteros, se le llama un programa de permutación.

Notación


Notación
expresión descripción
$[m] = n$ El m-ésimo trabajo de la sucesión es el trabajo n
$d_{[m]}$ Fecha de vencimiento (due date) del m-ésimo trabajo de la sucesión.

Resulta útil distinguir entre información a priori e información generada durante el proceso de programación. Utilizaremos minúsculas para la información a priori, que utilizaremos como entradas para el proceso de programación.

Para el SMPSP (single machine PSP, PSP de una sola máquina) tres datos son importantes:


Información a priori
Nombre Símbolo descripción
Tiempo de proceso $p_{j}$ Tiempo de proceso requerido por el trabajo j
Fecha de salida $r_{j}$ El tiempo a partir del cual el trabajo j está disponible para procesarse.
Fecha de vencimiento $d_{j}$ El tiempo a partir del cual el trabajo j debe estar terminado.

La información a posteriori representa salidas y la distinguiremos con mayúsculas:

Información a posteriori
Nombre Símbolo descripción
Tiempo de terminación $C_{j}$ El tiempo a partir del cual el trabajo j está terminado.
Tiempo de flujo $F_{j}$ El tiempo que el trabajo j dura en el sistema: $F_{j} = C_{j} - r_{j}$.
Retraso $L_{j}$ El tiempo que la terminación del trabajo j excede su fecha de vencimiento: $L_{j} = C_{j} - d_{j}$.

Observaciones


Cada medida de de desempeño es útil en distintos tipos de servicio. Si hablamos específicamente de retraso podemos decir que mide el nivel de conformidad con las fechas de vencimiento, tenemos así que si un trabajo está retrasado $L_{j} > 0$, y si un trabajo se termina antes de tiempo $L_{j} < 0$. Regularmente hay penalizaciones de algún tipo si $L_{j} > 0$, pero no siempre hay beneficios si $L_{j} < 0$, y para estos casos es útil usar otra medida:

Tardanza ($T_{j}$): El retraso de un trabajo si incumple la fecha de vencimiento, y cero en otro caso. $T_{j} = max\{0, L_{j}\}$

Las medidas anteriores miden el desempeño individual de un trabajo; los programas suelen tener medidas de desempeño unidimensionales que están en función de alguna de las medidas anteriores.
Tiempo de flujo total: $F = \sum_{j=1}^{n} F_{j}$
Tardanza total: $T = \sum_{j=1}^{n} T_{j}$
Máximo tiempo de flujo: $F_{max} = \max\limits_{1 \leq j \leq n} \{ F_{j}\}$
Máximo tardanza: $T_{max} = \max\limits_{1 \leq j \leq n} \{ T_{j}\}$
Número de trabajos tardíos: $U = \sum_{j=1}^{n} \delta (T_{j})$
Máximo tiempo de terminación (mejor conocido como makespan): $C_{max} = \max\limits_{1 \leq j \leq n} \{ C_{j}\}$ 

Donde $\delta (x) = \begin{cases}1 & x > 0 \\ 0 & \text{en otro caso} \end{cases}$

Bajo las suposiciones del SMPSP (C1 a C7), $C_{max} = F_{max} = \sum{p_{j}}$

Usando esta notación resulta conveniente referirse al problema de minimización del tiempo de flujo total como el problema F, y de manera análoga para el problema T, problema $C_{max}$, etc.

La contribución de cada trabajo a la función objetivo puede ser directa o indirecta. Por ejemplo, el tiempo total de flujo es simplemente la suma del tiempo de flujo de cada trabajo. En este tipo de función cada trabajo hace una contribución directa a la medida de desempeño, pues cada tiempo de flujo es parte de la suma. Sin embargo, para el problema $F_{max}$ algunos trabajos solamente hacen una contribución indirecta a la medida de desempeño, pues un trabajo $j$ puede no ser el que tiene el máximo flujo; pero puede ser el causante de un retraso del que sí lo tiene. Para fines de interpretación es útil transformar las medidas "totales" en medidas promedio (a final de cuentas el óptimo es el mismo pues solamente se está multiplicando la función objetivo por una constante).

Cada una de estas medidas de desempeño (MD) es una función del tiempo de terminación de cada trabajo.

$ Z = f(C_1, C_2, …, C_n)$
Y pertenecen a una clase de medidas de desempeño llamada "medidas regulares". Una medida Z es regular si:

  1. El objetivo es minimizar Z, y
  2. Z solamente puede aumentar si aumenta al menos un $C_i$ (tiempo de terminación) del programa.
Más formalmente, supóngase que $Z = f(C_1, C_2, …, C_n)$ es el valor de la medida que caracteriza el programa S, y que $ Z' = f(C_1', C_2', …, C_n')$ representa el valor de la misma medida en un programa distinto S'. Entonces Z es regular si y solo sí:
$Z' > Z \implies C_j'>C_j$ para algún trabajo $j$
Todas las medidas compuestas que hemos mencionado son medidas regulares, igual que muchos criterios de programación popularmente utilizados. En lo que resta lidiaremos mayormente con medidas regulares (eso hasta que toquemos el tema de heurísticas ;) ). La idea de las restricciones que estamos imponiendo es que usualmente es deseable trabajar con un conjunto limitado de programas, que se llama el conjunto dominante, de tal manera que no tengamos que buscar en el espacio de todos los programas posibles sino en uno más conveniente. Para verificar que un conjunto D es un conjunto dominante para MDs regulares, se puede razonar lo siguiente:


  1. Considere un programa arbitrario S (Con tiempos de terminación $C_j$) que no está en D
  2. Muestre que existe un programa S' en D tal que  $C_j' \leq C_j $ $\forall j$
  3. Por lo que $Z' \leq Z$ para cualquier medida regular, entonces S' es al menos tan bueno como S
  4. Por lo tanto, y si nuestro objetivo es buscar un programa óptimo, basta con considerar el conjunto de programas dominantes D.
Por ejemplo, la condición C6 puede relajarse para permitir tiempo muerto, pero insertar tiempo muerto jamás mejorará el mejor programa, en otras palabras podemos descartar los programas con tiempos muertos agregados del conjunto dominante, pero esto lo demostraremos en la siguiente publicación.

Resúmen

  • En esta publicación describimos un problema de programación funadmental: el de una sola máquina. 
  • Más específicamente tratamos con un problema de permutación. 
  • Definimos medidas de desempeño estándar por unidades de trabajo y compuestas o agregadas.
  • Definimos las medidas regulares ("coincidentemente", las medidas que ya habíamos definido también son regulares)
  • También reducimos el innecesariamente amplio espacio de búsqueda restringiéndonos a un conjunto dominante.
  • Encontramos una serie de condiciones que nos ayudarán a hacer muchas demostraciones de manera metódica para desarrollar la teoría de programación.