The graphical user interface (GUI) has become the prime means for interacting with computing systems. It leverages human perceptual and motor capabilities for elementary tasks such as command ...exploration and invocation, information search, and multitasking. For designing a GUI, numerous interconnected decisions must be made such that the outcome strikes a balance between human factors and technical objectives. Normally, design choices are specified manually and coded within the software by professional designers and developers. This article surveys combinatorial optimization as a flexible and powerful tool for computational generation and adaptation of GUIs. As recently as 15 years ago, applications were limited to keyboards and widget layouts. The obstacle has been the mathematical definition of design tasks, on the one hand, and the lack of objective functions that capture essential aspects of human behavior, on the other. This article presents definitions of layout design problems as integer programming tasks, a coherent formalism that permits identification of problem types, analysis of their complexity, and exploitation of known algorithmic solutions. It then surveys advances in formulating evaluative functions for common design-goal foci such as user performance and experience. The convergence of these two advances has expanded the range of solvable problems. Approaches to practical deployment are outlined with a wide spectrum of applications. This article concludes by discussing the position of this application area within optimization and human-computer interaction research and outlines challenges for future work.
We consider an optimization problem of sequencing the operations of cranes that are used for internal movement of containers in maritime ports. Some features of this problem have been studied in the ...literature as the stacker crane problem (SCP). However, the scope of most literature (including SCP) is restricted to minimizing the route or distance traveled by cranes and the resulting movement-related costs. In practice, cargo containers are generally stacked or piled up in multiple separate columns, heaps or stacks at ports. So, the cranes need to often rearrange or shuffle such container stacks, in order to pick up any required container. If substantial re-stacking is involved, cranes expend considerable effort in container stack rearrangement operations. The problem of minimizing the total efforts/time of the crane must therefore account for both – the stack rearrangement costs and also the movement-related (route distance) costs. The consolidated problem differs from standard route distance minimization situations if stack rearrangement activities are considered. We formally define the consolidated problem, identify its characteristic features and hence devise suitable models for it. We formulate several alternative MIP approaches to solve the problem. We compare the performance of our MIP formulations and analyze their suitability for various possible situations.
Whenever sets of objects are piled up in heaps, columns or stacks, any rearrangement of these objects requires substantial amount of time, effort and cost. In this paper, we study the problem of ...optimizing such “stack-rearrangement operations” when multiple similar objects or blocks need to be rearranged. We discuss the problem in the context of yard crane operations in maritime ports, where cargo containers are stored and fetched by yard cranes. We intend to minimize the crane operations that are required during container stack rearrangement by yard cranes. This paper defines the underlying abstract mathematical problem and proves its computational complexity. Thereafter, we propose suitable mathematical models for the problem and devise several (exact) approaches to solve it. We provide several families of new problem data instances and the prove the efficacy of our algorithms by doing extensive computational analysis over the data instances.
Foraging-based optimization of menu systems Dayama, Niraj Ramesh; Shiripour, Morteza; Oulasvirta, Antti ...
International journal of human-computer studies,
July 2021, 2021-07-00, Letnik:
151
Journal Article
Recenzirano
Odprti dostop
•This paper presents a novel integer programming formulation for the hierarchical menus.•This paper introduces a novel objective function based on information foraging theory.•This technique yields ...usable, well-ordered command hierarchies from a single model.•This paper models the hierarchical menu design problem as a combination of the exact set covering problem and the assignment problem.•The performance of computationally designed menus was ∼25% faster to use than existing commercial designs.
The problem of computational design for menu systems has been addressed in some specific cases such as the linear menu (list). The classical approach has been to model this problem as an assignment task, where commands are assigned to menu positions while optimizing for users’ selection performance and grouping of associated items. However, we show that this approach fails with larger, hierarchically organized menus because it does not take into account the ways in which users navigate hierarchical structures. This paper addresses the computational menu design problem by presenting a novel integer programming formulation that yields usable, well-ordered command hierarchies from a single model. First, it introduces a novel objective function based on information foraging theory, which minimizes navigation time in a hierarchical structure. Second, it models the hierarchical menu design problem as a combination of the exact set covering problem and the assignment problem, organizing commands into ordered groups of ordered groups. The approach is efficient for large, representative instances of the problem. In a controlled usability evaluation, the performance of computationally designed menus was ∼25% faster to use than existing commercial designs. We discuss applications of this approach for personalization and adaptation.
New approaches for solving the convoy movement problem Mokhtar, Hamid; Krishnamoorthy, Mohan; Dayama, Niraj Ramesh ...
Transportation research. Part E, Logistics and transportation review,
January 2020, 2020-01-00, Letnik:
133
Journal Article
Recenzirano
The convoy movement problem (CMP) involves the routing and scheduling of a large number of vehicles and personnel across a network. A convoy is a group of (typically, army) vehicles and personnel ...that travel together as a group. Given the nature and context of these movements, it is necessary to avoid convoys crossing each other at a node, overtaking, or crossing each other on a road as they travel in the network from their individual origins to their destinations. The lengths and travel speeds are also major factors that determine the optimal travel paths and schedules for these convoys. In this paper, we review different variants of the CMP in the literature. We then propose a generalised problem statement for the CMP that accommodates all common variants. This generalised problem definition addresses several important side constraints that typically occur in real-world problems. We adapt and enhance existing formulations of the CMP in such a way that the generalised version can also be modelled. Further, we propose new approaches for solving large instances of the generalised CMP. Our computational experiments show that the techniques introduced in this paper substantially outperform existing approaches in the literature. We also generate a new dataset for the generalised CMP that provides a framework for the examination of various approaches for the CMP with a wider set of side constraints.
This paper addresses the problem of designing efficient logistical arrangements for preparation and delivery of edible food (by a voluntary organization). The short shelf-life of edible, ready-to-eat ...food items complicates the provisioning and distribution networks. The design of the underlying logistical system constitutes an interesting combinatorial optimization problem. Our paper explains the problem background and rigorously defines the underlying mathematical problem. Thereafter, we develop a set of algorithms/techniques (exact and heuristic) to solve the problem faster. We blend the stronger lower bounds (obtained from an alternate MIP formulation) with better upper bounds (obtained using a fast and efficient heuristic approach) to develop a new exact technique. We report the detailed results from computational analysis of our new techniques.
Foraging-based optimization of pervasive displays Montoya Freire, Maria L.; Potts, Dominic; Dayama, Niraj Ramesh ...
Pervasive and mobile computing,
April 2019, 2019-04-00, Letnik:
55
Journal Article
Recenzirano
Odprti dostop
The article addresses a key challenge in the design of content for pervasive displays: how to engage passers-by who have limited time and attention? To achieve this, we apply a novel approach for ...computational design of interesting display content using tiled layouts. We present a model of display foraging based on information foraging theory to describe the behavior of a rational but time-limited user looking at a display. Accordingly, our work aims to maximize the information gain for tiled displays. This complex problem is divided into two phases: (1) generating designs of tiled layouts and (2) assigning content options to individual tiles based on what predicted by display foraging. Accordingly, a proof-of-concept system was realized then evaluated computationally and empirically with a control study and field study. The results show that the proposed system can engage significantly more people than typical digital signage.
In this paper, we extend job scheduling models to include aspects of history-dependent scheduling, where setup times for a job are affected by the aggregate activities of all predecessors of that ...job. Traditional approaches to machine scheduling typically address objectives and constraints that govern the relative sequence of jobs being executed using available resources. This paper optimises the operations of multiple unrelated resources to address sequential and history-dependent job scheduling constraints along with time window restrictions. We denote this consolidated problem as the general precedence scheduling problem (GPSP). We present several applications of the GPSP and show that many problems in the literature can be represented as special cases of history-dependent scheduling. We design new ways to model this class of problems and then proceed to formulate it as an integer program. We develop specialized algorithms to solve such problems. An extensive computational analysis over a diverse family of problem data instances demonstrates the efficacy of the novel approaches and algorithms introduced in this paper.
•Detailed explanation of differences between GPSP and Block-world problem has been submitted within the response document.•Summary of differences between GPSP and block-world problem has been included in the paper.•Justification for using only first log(n) and not all i, j, K combinations has been included in the paper.•Mistakes in write-up have been corrected as pointed out by reviewers.
Computational design of menu systems has been solved in limited cases such as the linear menu (list) as an assignment task, where commands are assigned to menu positions while optimizing for for ...users selection performance and distance of associated items. We show that this approach falls short with larger, hierarchically organized menu systems, where one must also take into account how users navigate hierarchical structures. This paper presents a novel integer programming formulation that models hierarchical menus as a combination of the exact set covering problem and the assignment problem. It organizes commands into ordered groups of ordered groups via a novel objective function based on information foraging theory. It minimizes, on the one hand, the time required to select a command whose location is known from previous usage and, on the other, the time wasted in irrelevant parts of the menu while searching for commands whose location is not known. The convergence of these two factors yields usable, well-ordered command hierarchies from a single model. In generated menus, the lead (first) elements of a group or tab are good indicators of the remaining contents, thereby facilitating the search process. In a controlled usability evaluation, the performance of computationally designed menus was 25 faster than existing commercial designs with respect to selection time. The algorithm is efficient for large, representative instances of the problem. We further show applications in personalization and adaptation of menu systems.
Carrier Ethernet is rapidly being deployed in the metropolitan and core segments of the transport network. One of the emerging flavors of Carrier Ethernet is the IEEE 802.1Qay PBB-TE or Provider ...Backbone Bridging-Traffic Engineering standard. PBB-TE relies on the assignment of a network-specific Virtual Local Area Network (VLAN) tag, called the Backbone VLAN ID or BVID that is used in conjunction with a backbone Media Access Control (MAC) address for forwarding. The 12-bit BVID along with 48-bit Backbone MAC address are used to forward an Ethernet frame. The assignment of BVIDs in a network is critical, given that there are only 4094 possible assignments, especially for those paths that are overlapping in the network graph and incident at the same destination. While the only way to scale is to reuse BVIDs, this method can lead to a complication if the same BVID is allocated to an overlapping path. To the best of our knowledge, this is the first instance of isolating this problem of limited BVID availability which rises only due to graphical overlap between services. We formulate and solve this as a constrained optimization problem. We present optimal and heuristic algorithms to solve the BVID problem. The optimal approach solves the `static' case, while the heuristic can solve both the `static' and the `dynamic' cases of the BVID allocation problem. Results show that the developed heuristics perform close to the optimal and can be used in commercial settings for both the static and dynamic cases.
PDF
