Search

This paper introduces a problem in which the state of a system needs to be determined through costly tests of its components by a limited number of testing units and before a given deadline. We also consider a closely related search problem in which there are multiple searchers to find a target before a given deadline. These natural generalizations of the classical sequential testing problem and search problem are applicable in a wide range of time-critical operations such as machine maintenance, diagnosing a patient, and new product development. We show that both problems are NP-hard, develop a pseudo-polynomial dynamic program for the special case of two time slots, and describe a partial-order-based as well as an assignment-based mixed integer program for the general case. Based on extensive computational experiments, we find that the assignment-based formulation performs better than the partial-order-based formulation for the testing variant, but that this is the other way round for the search variant. Finally, we propose a pairwise-interchange-based local search procedure and show that, empirically, it performs very well in finding near-optimal solutions.

Supply chain coordination problems involve a number of actors, namely suppliers, manufacturers, 3PL providers, and customers. In a typical scenario, there are m manufacturers (modeled as single machines), each of which processes a specific set of jobs (products). After their processing is completed, products are shipped to a customer by means of vehicles. The set of jobs assigned to the same vehicle in one delivery is a delivery batch. The problem consists in concurrently finding a production schedule of the jobs on the machines, a partition of jobs into delivery batches, and an assignment of delivery batches to vehicles, so that jobs are delivered within their deadlines and total costs are minimized. We focus on a scenario characterized by fixed departure times and inventory holding costs. The former means that a set of departure times is given, and for each of them there is a (given) number of vehicles, possibly having limited capacity. The latter means that each job incurs a cost proportional to the length of the time span from the job completion time to its delivery departure time. Within this general framework, in this paper we report complexity results concerning two special cases, namely (i) when each manufacturer imposes a certain production sequence to the 3PL, and (u) when there is a single manufacturer, processing times are all equal to 1, there are no binding deadlines and there are no fixed delivery costs.

The problem of assigning information packets of different services to time slots of a radio frame is addressed. Packet sizes are divisible, and a maximum time slot to which a packet can be assigned is given. We present a polynomial-time scheduling algorithm maximizing the number of scheduled packets.

In this paper, we address a deterministic scheduling problem in which two agents compete for the usage of a single machine. Each agent decides on a fixed order to submit its tasks to an external coordination subject, who sequences them according to a known priority rule. We consider the problem from different perspectives. First, we characterize the set of Pareto-optimal schedules in terms of size and computational complexity. We then address the problem from the single-agent point-of-view, that is, we consider the problem of deciding how to submit one agent's tasks only taking into account its own objective function against the other agent, the opponent. In this regard, we consider two different settings depending on the information available to the agents: In one setting, the considered agent knows in advance all information about the submission sequence of the opponent; and in the second setting (as in minimax strategies in game theory), the agent has no information on the opponent strategy and wants to devise a strategy that minimizes its solution cost in the worst possible case. Finally, we assess the performance of some classical single-agent sequencing rules in the two-agent setting.

This paper investigates possible implementations of the autonomous agents concept in flexible manufacturing control. The implementation issues and the effectiveness of different control architectures and algorithms are analyzed by means of a simulation model of a flexible job shop. Extensive experimental results are reported, allowing the evaluation of the trade-off between the degree of autonomy and system performance.

This research aims at supporting hospital management in making prompt Operating Room (OR) planning decisions, when either unpredicted events occur or alternative scenarios or configurations need to be rapidly evaluated. We design and test a planning tool enabling managers to efficiently analyse several alternatives to the current OR planning and scheduling. To this aim, we propose a decomposition approach. More specifically, we first focus on determining the Master Surgical Schedule (MSS) on a weekly basis, by assigning the different surgical disciplines to the available sessions. Next, we allocate surgeries to each session, focusing on elective patients only. Patients are selected from the waiting lists according to several parameters, including surgery duration, waiting time and priority class of the operations. We performed computational experiments to compare the performance of our decomposition approach with an (exact) integrated approach. The case study selected for our simulations is based on the characteristics of the operating theatre (OT) of a medium-size public Italian hospital. Scalability of the method is tested for different OT sizes. A pilot example is also proposed to highlight the usefulness of our approach for decision support. The proposed decomposition approach finds satisfactory solutions with significant savings in computation time.

This paper concerns the problem of optimally scheduling a set of appliances at the end-user premises. In the context of electricity smart grids, the electric energy fee varies over time and the user may receive a reward from an energy aggregator if he/she modifies his/her consumption profile during certain time intervals. The problem is to schedule the operation of the appliances taking into account overall costs, climatic comfort level and timeliness. We devise a MILP model and a heuristic algorithm accounting for a typical household user. Several numerical simulation results are reported, showing that the problem can be efficiently solved in real-life instances.

This paper deals with the problem of part input sequencing in an automated flow shop system. The system consists of one input/output station, two machines and one AGV, which is used for all part transfer operations throughout the cell. The objective is the minimization of the makespan. This cell architecture has recently received considerable attention in the literature. Here we consider the case in which the two machines are equipped by a swapping device, allowing the AGV to exchange a new part for the one released by the machine. A similar device exists for the input/output station. If the transportation times are small enough, the problem can be formulated as a two-machine flow shop with limited intermediate buffer, which is NP-hard. Here we analyze the problem in the context of lot processing, i.e., when identical parts must be processed consecutively. Each set of identical parts forms a lot. The number of parts in the lot is the size of the lot. If the size of the ith lot is larger than a value b*i, ...

The routing mix problem in flexible assembly systems is considered. The problem consists of assigning the operations for each part to the machines, with the two objectives of balancing the machine workloads and minimizing the burden of the transportation system. These two objectives are sometimes conflicting, since the latter tends to support assigning operations to the same machine(s) as much as possible, and this may be bad for workload balancing. A linear programming problem is presented that, given a constraint on the workload of each machine, finds one solution that minimizes the overall time spent moving the parts from one machine to another. Since such a linear program may have an exponential number of variables, an efficient column generation technique to solve the problem is devised. The efficiency of the method is validated by experiments on a large number of random problems.

The design and balancing of a line which assembles car heaters is examined. To accomplish a balance, the general assembly line balancing model is extended to cope with some restrictions due to the physical structure of the production line: namely, incompatibilities among operations and operations that must be necessarily performed by certain work stations. A polynomial time dynamic programming algorithm is provided to balance the workloads among the work stations taking into account these additional constraints, exploiting the special structure of the operation graph. The algorithm was applied to two designs: a single line on which all the heater components are assembled, and also to several segmented lines, which collectively assemble heaters. Demand volume variations are also addressed.

This paper addresses Operating Room (OR) planning policies in elective surgery. In particular, we investigate long-term policies for determining the Master Surgical Schedule (MSS) throughout the year, analyzing the tradeoff between organizational simplicity, favored by an MSS that does not change completely every week, and quality of the service offered to the patients, favored by an MSS that dynamically adapts to the current state of waiting lists, the latter objective being related to a lean approach to hospital management. Surgical cases are selected from the waiting lists according to several parameters, including surgery duration, waiting time and priority class of the operations. We apply the proposed models to the operating theater of a public, medium-size hospital in Empoli, Italy, using Integer Linear Programming formulations, and analyze the scalability of the approach on larger hospitals. The simulations point out that introducing a very limited degree of variability in MSS in terms of OR sessions assignment can largely pay off in terms of resource efficiency and due date performance.

The allocation of tools to machines determines potential part routes in flexible manufacturing systems. Given production requirements and a minimum feasible set of tools, the decision of how to fill vacant slots in tool magazines to maximize routing flexibility is shown to be a minimum cost network flow problem for the cases when routing flexibility is a function of the average workload per tool aggregated over tool types, or of the number of possible routes through the system. A linear programming model is then used to plan a set of routes for each part type so as to minimize either the material handling requirement or the maximum workload on any machine. The impact of these tool addition strategies on the material handling and workload equalization is investigated and computational results presented. The advantage of the overall approach is computational simplicity at each step and the ability to react to dynamic changes.

Mixed model assembly lines are becoming increasingly used in manufacturing facilities to meet the diversified demands of customers. In this paper we deal with syncronous flow lines and wish to determine the job input sequence minimizing total tardiness. A ILP formulation of the problem is given. We prove the strong NP-hardness of the problem, we try to solve the linear relaxation of the problem and then introduce a number of cutting planes to solve the separation problem. Computational results confirm the effectiveness of the procedure.

This paper concerns the problem of optimally scheduling a set of appliances at the end-user premises. The user's energy fee varies over time, and moreover, in the context of smart grids, the user may receive a reward from an energy aggregator if he/she reduces consumption during certain time intervals. In a household, the problem is to decide when to schedule the operation of the appliances, in order to meet a number of goals, namely overall costs, climatic comfort level and timeliness. We devise a model accounting for a typical household user, and present computational results showing that it can be efficiently solved in real-life instances.

In a plant for automobile assembly, sub-assemblies are produced in shops consistingof sequential groups of parallel workstations. The problem of optimally sequencing n jobs in such an environmentis a generalization of the flow shop problem. In this paper a new dispatching rule is proposed that also considersjobs that have not yet completed the previous operation. The next job to be machined in the successive stage is selected by solving an instance of a bottleneck assignment problem based on the actual state of the shop. The results are verified via simulation of a real automobile assembly line

In this paper, a mathematical model for the allocation of sales representatives is presented. The model takes into account some special features of pharmaceutical marketing, such as customer profiling (physicians), sales response functions and multi-product (drug) promotion procedures. The main peculiarity of the model is that it is suitable to those markets (such as European markets) where the detailed information about historical physician prescriptions is not available to pharmaceutical companies. A heuristic procedure has been designed and run to plan nationwide representative calls to more than 46000 physicians. A computational study, based on real data from a major pharmaceutical company, shows the feasibility of this algorithmic approach, resulting in significantly enhanced productivity. Moreover, the algorithm can be also employed as a tool to evaluate costly strategic options concerning sales force sizing and training

The problem of task assignment for a class of flexible manufacturing cells is considered. The cell is designed for cyclic production of one product. The product is characterized by a sequence of operations of given length and each requiring a robot: the problem is therefore to allocate the operations to the robots in order to maximize the throughput. The problem of finding a task assignment such that the parts are never in a waiting state is discussed. Notice that, if such assignment exists, the maximum theoretical throughput is achieved. The complexity of the problem for some structures of the system by means of graph-theoretical models.

The problem of part routing and scheduling in flexible manufacturing systems is considered with the goal of increasing the throughput. The flexible system considered is strongly characterized by the inclusion of assembly among the manufacturing operations to be performed on a mix of part batches. In particular, the logic structure of some basic decision problems is indicated through a set of combinatorial models. Two basic assembly problems characterized by batches of large and small size, respectively, are analyzed. >

In this paper we consider the problem of creating batches of parts, to be processed in a flexible manufacturing cell, and scheduling their operations. We consider the case in which the system consists of one machine and at most k parts may be present in the system at the same time. Given that each part requires a sequence of operations, and each operation requires a given tool, the objective is to minimize the total number of setups. We develop a heuristic algorithm for its solution and we present an extensive computational experience.

In UTRA-TDD, packets with different formats and quality-of-service (QoS) requirements are sent across the air interface organized into radio frames. We propose a frame-by-frame exact downlink scheduling algorithm based on dynamic programming, considering different traffic classes with their QoS levels.

An approach to part-type selection and scheduling of parts in a two-machine flexible-flow line is presented. It consists of first selecting a small number of part types for simultaneous production (in suitable ratios in order to balance the workloads among the machines), and then scheduling the parts of each batch in order to minimize both completion time as well as the maximum level of in-process inventory required. The system consists of two machines, and all of the parts visit the two machines in the same order. Some advantages of the approach presented include management effectiveness and simplicity, in addition to other benefits inherent in a dynamic and flexible approach to part-type selection (such as a higher utilization of the machines, a smoother tool-changing activity, etc.). >

In a clothing industry, clothes are produced by assembling fabric cutouts. Fabric rolls on a line, and is cut by automated machines arranged along the line. A fabric cutout f j requiring time P j to be cut, is available for cutting on the first machine at a release date r 1 j , and must be completed, on the same machine, within a deadline D 1 j . On machine M i , i = 2, …, m, release dates and deadlines related to the cutout f j are r 1 j = r 1 j + Δ( i - 1) and D i j = D i j + Δ( i - 1) respectively, where Δ is a constant factor depending on the speed rate of the fabric. A set-up time occurs on a machine, when switching from one cutout to another. The problem of assigning and scheduling cutting tasks to the minimum number of machines is addressed.

In this paper we consider a manufacturing problem arising in a robotic cell for aircraft panels assembly. An initial technological analysis has shown that some mechanical assembly phases, which involve a huge amount of riveting and screwing operations, can be automated. The motivation of this research is to find the most profitable sequencing of the operations from the viewpoint of throughput time. In particular, we focus on the set-up activities related to switching between operations. The problem is to find the permutation of operations such that the overall switching time is a minimum. In the situation on hand, major precedence constraints among the operations hold. The problem is formulated as an instance of the well-known 'sequential ordering problem', for which we propose a tabu search solution heuristic. In this paper we report on both the modelling process and the solution procedures.

This paper deals with the material flow management in a large-scale manufacturing process, namely the assembly of automobiles in a highly automated plant in Italy. After a detailed description of the plant from the viewpoint of material flow issues, the modeling process and the methodologies employed to address the problems are illustrated. The decision models were validated by means of simulations of the real plant in several different production scenarios (varying demand volume and mix, resource availability etc.).

In this paper we examine the issue of tool management in a flexible manufacturing cell. The type of system considered here is typical of mechanical manufacturing, in which large metallic parts are loaded on the machines and are not moved until processing completion. The architecture of the cell is characterized by the absence of on-board tool magazines on the machines. Although this permits the continuous maintenance and inspection of the tools and typically results in cost and workspace savings, it calls for more complex tool handling procedures. We present a heuristic to address the overall problem of assigning parts to machines, sequencing parts on each machine, and synchronizing tool movements. The results indicate that our method provides near-optimal solutions in terms of makespan and mean flow time. Further, we observe that the solution procedure is at least one order of magnitude faster than the approach currently used and also results in a much better mean flow time.

Flexible manufacturing systems (FMSs) typically contain a set of numerically controlled workstations and a material handling system coordinated by a central controller for the purpose of simultaneous production of a variety of part types. General purpose machining centers are used with automatic tool change and part load/unload capability to permit quick, automated changeovers from workpiece to workpiece and part type to part type. The FMS represents a significant investment in training, hardware and software. This investment is justified by the ability of the system to produce a variety of high quality parts with short lead times while requiring less floor space than traditional systems. The key here is the flexibility of the system to change tools and route parts as needed to maintain high effective utilization rates for machines as the part mix varies. The average FMS manufactures 80 different parts with machines cutting over 75% of the time (Jaikumar and Van Wassenhove [1]).

In this paper a set of new algorithms for the No-Wait Flow Shop problem is proposed for processing a mix of s lots, different in dimensinn and part-type, on a Pipeline Manufacturing System: in the two-machines case, an O(s log s) algorithm is given, yielding a very small bound on the relative error. The larger the lots, the better the approximation and the greater the time saving with respect to the exact algorithm due to Gilnlore and Gomory. Notice that lot sizes need not be identical and the exact duration of the operations is not required (only the knowledge of the relative ranking of the operation times is needed). In the m-machines case, with the additional constraint of no machine idle times (i.e. neither the parts nor the machines have to wait), an O(ms) algorithm is given; if such solution exists, it corresponds to both throughput maximization and inventory cost mininlization.

Some optimization models for the problem of tool management in flexible manufacturing cells are presented. The cell considered consists of two machines (working centers) in charge of executing a set of part programs. The tools required by the machining operations are located in a central tool magazine and are moved to the machines by a tool handling system consisting of two shuttles and one robot. The robot picks and places the tools from/in the magazine; each shuttle exchanges the tools with the robot and with the machine. The problem is to synchronize the robot and shuttle moves in order to maximize the cell productivity (minimize the machines' idle time). Two different models are proposed for the situation in which a configuration of tools in the magazine is given and in which a budget for tool purchasing is fixed. >

UTRA-TDD is one of the adopted air interfaces for third-generation (3G) mobile communication systems. In UTRA-TDD, packets with different quality of service (QoS) requirements need to be managed. We formulate the downlink packet scheduling problem in terms of dynamic programming by taking into account all the allocation constraints. Hence, we define a frame-by-frame exact downlink scheduling algorithm to support Web interactive and voice traffics, named 2-class optimal packet scheduling (2OPS). The good performance of 2OPS has been supported through the capacity improvement with respect to other protocols appeared in the literature.