One more generalization of the assignment problem – Københavns Universitet

One more generalization of the assignment problem

Algo-talk by Prof. Stanislaw Walukiewicz Systems Research Institute, Polish Academy of Sciences


One among many origins of the assignment problem is the generally-recognised (Classical) Production Line (CPL), introduced by Henry Ford in auto industry in 1913. Before then, cars were produced by highly skilled craftsmen in so-called production circles. Ford proved in practice that highly skilled craftsmen are not necessary in car production and that what matters most is organisation. With proper organisation, simple workers can produce sophisticated cars. So organization matters on CPL.  In the assignment problem in this context we are looking for an optimal assignment of workers to jobs/operations (1-1 mapping) such that the longest job is executed in the shortest possible time and, therefore CPL runs at the highest possible speed.

In 2006 Walukiewicz introduced the idea of Virtual Production Line (VPL) as a model/tool for the analysis of creative/problem solving processes and demonstrated that it could be considered as a natural expansion of the CPL concept. Experts or teams of experts connected by modern ICT network (in most cases just the Internet) may be located in different parts of the world, working on a given VPL to solve a problem, perhaps initially not so well defined. In contrast to CPL however, experts on VPL are chiefly thinking, among others, about how to divide the problem into a number of tasks, about the sequence tasks, etc.  - we will call this self-organisation of VPL. VPL will then consist of three parts: a division of labour (with CPL, it is simple partition of labour into jobs), modern ICT network and self-organization. We claim that in a knowledge-based economy VPLs, perhaps not so well designed, are almost everywhere and self-organization as a way of improvement of a given VPL is invaluable. So self-organization matters very much on VPL.

The main objective of this talk is to define as precisely as possible the problem of assignment of people to jobs on VPL, or in other words, how to assign experts to tasks on a VPL given its possible self-organisation(s). We suggest that they are assigned according to proximity principle. Proximity literally means nearness, closeness, contiguity and propinquity. We will use this proposition to describe relations between different experts working on a given VPL. Like capital, proximity is complex and multidimensional. In fact it is 4-dimensional and depends on time, as capital does. Further, proximity is a subjective concept.  First we will assign experts to tasks on a VPL according to cognitive (technological) proximity.

This talk is organized as a self-contained unit. All assumptions, definitions and concepts will be described and discussed in it in detail and an example of VPL in the ICT sector will be provided.