A scheduling problem for a novel container transport system: a case of mobile harbor operation schedule

Mobile Harbor (MH) is a movable floating platform with a container handling system on board so that it can load/discharge containers to/from an anchored container ship in the open sea. As with typical quay crane operation, an efficient schedule for its operation is a key to enhancing its operational productivity. A MH operation scheduling problem is to determine a timed sequence of loading/discharging tasks, assignment of MH units to each task, and their docking position, with an objective of minimizing the makespan of a series of incoming container ships. A mixed integer programming model is formulated to formally define the problem. As a practical solution method to the problem, this paper proposes a rule-based algorithm and a random key based genetic algorithm (rkGA). Computational results show that the rkGA method produces a better-quality solution than the rule-based method, while requiring longer computation time.     

Optimization of glucose isomerase reactor: optimum operating temperature mode

The optimum temperature operation mode required to achieve high fructose productivity is studied for immobilized glucose isomerase (GI) packed bed reactor. In this study, the reactor design equation based on reversible Michaelis-Menten kinetics assumes both thermal enzyme deactivation and substrate protection. The optimization problem is formulated as a discretized constrained nonlinear programming problem (NLP). The formulation is expressed in terms of maximization of fructose productivity as the objective function subject to reactor design equation, kinetic parameter equations, substrate protection factor equation and feasibility constraints. The constraints are discretized along the reactor operating period by employing piecewise polynomial approximations. Approximately 7% improvement in terms of fructose productivity is achieved when running the reactor at the optimum decreasing temperature operation mode as compared to the constant optimum isothermal operation.     

Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics

We investigate a difficult scheduling problem in a semiconductor manufacturing process that seeks to minimize the number of tardy jobs and makespan with sequence-dependent setup time, release time, due dates and tool constraints. We propose a mixed integer programming (MIP) formulation which treats tardy jobs as soft constraints so that our objective seeks the minimum weighted sum of makespan and heavily penalized tardy jobs. Although our polynomial-sized MIP formulation can correctly model this scheduling problem, it is so difficult that even a feasible solution can not be calculated efficiently for small-scale problems. We then propose a technique to estimate the upper bound for the number of jobs processed by a machine, and use it to effectively reduce the size of the MIP formulation. In order to handle real-world large-scale scheduling problems, we propose an efficient dispatching rule that assigns a job of the earliest due date to a machine with least recipe changeover (EDDLC) and try to re-optimize the solution by local search heuristics which involves interchange, translocation and transposition between assigned jobs. Our computational experiments indicate that EDDLC and our proposed reoptimization techniques are very efficient and effective. In particular, our method usually gives solutions very close to the exact optimum for smaller scheduling problems, and calculates good solutions for scheduling up to 200 jobs on 40 machines within 10 min.     

Aproximating static list schedules in dynamic multithreaded applications

List scheduling algorithms are known to be efficient when the application to be executed can be described statically as a Directed Acyclic Graph (DAG) of tasks. Regardless of knowing the entire DAG beforehand, obtaining an optimal schedule in a parallel machine is a NP-hard problem. Moreover, many programming tools propose the use of scheduling techniques based on list strategies. This paper presents an analysis of scheduling algorithms for multithread programs in a dynamic scenario where threads are created and destroyed during execution. We introduce an algorithm to convert DAGs, describing applications as tasks, into Directed Cyclic Graphs (DCGs) describing the same application designed in a multithread programming interface. Our algorithm covers case studies described in previous works, successfully mapping from the abstract level of graphs to the application environment. These mappings preserve the guarantees offered by the abstract model, providing efficient scheduling of dynamic programs that follow the intended multithread model. We conclude the paper presenting some performance results we obtained by list schedulers in dynamic multithreaded environments. We also compare these results with the best scheduling we could obtain with similar static task schedulers.     

A heuristic algorithm for the loading problem in flexible manufacturing systems

The paper considers the loading problem in flexible manufacturing systems (FMSs). This problem involves the assignment to the machine tools of all operations and associated cutting tools required for part types that have been selected to be produced simultaneously. The loading problem is first formulated as a linear mixed 0–1 program with the objective to minimize the greatest workload assigned to each machine. A heuristic procedure is presented in which an assignment of operations to machine tools is obtained by solving a parameterized generalized assignment problem with an objective function that approximates the use of tool slots required by the operations assigned to the machines. The algorithm is coded in FORTRAN and tested on an IBM-compatible personal computer. Computational results are presented for different test problems to demonstrate the efficiency and effectiveness of the suggested procedure.     

Schedule efficiency in a robotic production cell

In this paper, we analyze the efficiency of a given robot movement schedule for the case of a flow shop robotic production cell withm different machines, one input conveyor, and one output conveyor. We begin with the case of one-robot cells and extend our results to multirobot cells. The paper studies the efficiency of a movement schedule for identical parts by defining a movement network associated with this schedule. This network models any cell layout and applies to multirobot cells. Using the movement network, we propose two cycle time evaluation methods, the first using linear programming and the second based on finding a longest path. The latter method generates a procedure to obtain an analytical formula for the cycle time. We extend the proposed methods to study the efficiency of a given input sequence (schedule) for different parts, that is, to determine the sequence processing time. The results obtained here allow us to quickly evaluate the efficiency of any given feasible movement schedule, for identical or different parts.     

Capacity optimization and scheduling of a multiproduct manufacturing facility for biotech products

A general mathematical framework has been proposed in this work for scheduling of a multiproduct and multipurpose facility involving manufacturing of biotech products. The specific problem involves several batch operations occurring in multiple units involving fixed processing time, unlimited storage policy, transition times, shared units, and deterministic and fixed data in the given time horizon. The different batch operations are modeled using state‐task network representation. Two different mathematical formulations are proposed based on discrete‐ and continuous‐time representations leading to a mixed‐integer linear programming model which is solved using General Algebraic Modeling System software. A case study based on a real facility is presented to illustrate the potential and applicability of the proposed models. The continuous‐time model required less number of events and has a smaller problem size compared to the discrete‐time model. © 2014 American Institute of Chemical Engineers Biotechnol. Prog., 30:1221–1230, 2014     

Design of single assembly line for the delayed differentiation of product variants

Delayed Product Differentiation (DPD) can reduce the manufacturing complexities arising due to the proliferation of products variety. A new optimization model constructs the optimum layout of delayed differentiation assembly lines for a mix of products to be manufactured by the same system and optimizes the position of the differentiation points. This model employs a classification tool (Cladistics) used in biological analysis and modifies it for use in planning DPD assembly lines configurations in order to incorporate the assembly precedence constraints, required production rates of different product variants and existing production capacity of work stations. The optimum layout configuration ensures that the quantities required of different products are produced on the same line; while achieving balance, minimizing duplication of stations and maximizing the overall system utilization. The developed model has been applied to a group of automobile engine accessories normally assembled on different lines. The use of Cladistics to analyze product variants that are candidates for delayed assembly is an original approach for designing the assembly line layout and identifying the best differentiation points. It also helps rationalize the design of product variants and their features to further delay their assembly differentiation and achieve economy of scale without affecting their functionality.     

A job-shop scheduling approach for optimising sugarcane rail operations

The sugarcane transport system is very complex and uses a daily schedule, consisting of a set of locomotives runs, to satisfy the requirements of the mill and harvesters. The total cost of sugarcane transport operations is very high; over 35% of the total cost of sugarcane production in Australia is incurred in cane transport. Producing efficient schedules for sugarcane transport can reduce the cost and limit the negative effects that this system can have on the raw sugar production system. In this paper, the sugarcane rail operations are formulated as a blocking job shop scheduling problem. A mixed integer programming approach is used to formulate the shop job scheduling problem. Mixed integer programming and constraint programming search techniques are integrated for solving the problem. A case study is solved to test the approach.     

Part feeding at high-variant mixed-model assembly lines

The part feeding problem at automotive assembly plants deals with the timely supply of parts to the designated stations at the assembly line. According to the just-in-time principle, buffer storages at the line are frequently refilled with parts retrieved from a central storage area. In the industrial application at hand, this is accomplished by means of an internal shuttle system which supplies the various stations with the needed parts based on a given assembly sequence. The main objective is to minimize the required number of shuttle drivers. To solve this in-house transportation problem, a heuristic solution procedure is developed which is based on the decomposition of the entire planning problem into two stages. First, transportation orders are derived from the given assembly sequence. In the second stage, these orders are assigned to tours of the shuttle system taking transportation capacity restrictions, due dates and tour scheduling constraints into account. Numerical results show that the proposed heuristic solves even large-sized problem instances in short computational time. Benchmark comparisons with Kanban systems reveal the superiority of the proposed predictive part feeding approach.     

三层动态手术计划模型的构建

在静态的长期手术计划中,由于存在很多不确定性因素影响,使其很困难在实际中应用。文章提出一种动态三层手术计划排程,最上层为滚动资源分配模型,用线性规划模型为各科室合理分配手术室资源;中层采用多目标线性规划模型制定动态主手术计划;底层为在线调整模型,当意外情况出现时对动态手术计划进行调整。并结合某大型综合医院实情提供了数值算例,算例结果证明了模型的有效性。     

Integrated scheduling of elective surgeries and surgical nurses for operating room suites

Facing an acute shortage of surgical nurses, operating room suites in China are more and more aware of the need to use surgical nurses efficiently. This goal is hard to achieve due to the strong interactions between the nurse and the surgery scheduling process. This paper addresses the benefit of integrating elective surgery and surgical nurse scheduling in terms of nurse utilization. First, an integer programming (IP) model is proposed to schedule elective surgeries and surgical nurses simultaneously. Then an efficient genetic algorithm (GA) is proposed based on the IP formulation due to the computational complexity of the integrated scheduling problem. A case study using real-life data is presented to validate the performance of the integrated approaches (the IP model and the GA) by comparing them with a two-stage approach that schedules elective surgeries and surgical nurses sequentially.     

MIP formulations for an application of project scheduling in human resource management

In the literature, various discrete-time and continuous-time mixed-integer linear programming (MIP) formulations for project scheduling problems have been proposed. The performance of these formulations has been analyzed based on generic test instances. The objective of this study is to analyze the performance of discrete-time and continuous-time MIP formulations for a real-life application of project scheduling in human resource management. We consider the problem of scheduling assessment centers. In an assessment center, candidates for job positions perform different tasks while being observed and evaluated by assessors. Because these assessors are highly qualified and expensive personnel, the duration of the assessment center should be minimized. Complex rules for assigning assessors to candidates distinguish this problem from other scheduling problems discussed in the literature. We develop two discrete-time and three continuous-time MIP formulations, and we present problem-specific lower bounds. In a comparative study, we analyze the performance of the five MIP formulations on four real-life instances and a set of 240 instances derived from real-life data. The results indicate that good or optimal solutions are obtained for all instances within short computational time. In particular, one of the real-life instances is solved to optimality. Surprisingly, the continuous-time formulations outperform the discrete-time formulations in terms of solution quality.     

A line-balancing strategy for designing flexible assembly systems

We present a rough-cut analysis tool that quickly determines a few potential cost-effective designs at the initial design stage of flexible assembly systems (FASs) prior to a detailed analysis such as simulation. It uses quantitative methods for selecting and configuring the components of an FAS suitable for medium to high volumes of several similar products. The system is organized as a series of assembly stations linked with an automated material-handling system moving parts in a unidirectional flow. Each station consists of a single machine or of identical parallel machines. The methods exploit the ability of flexible hardware to switch almost instantaneously from product to product. Our approach is particularly suitable where the product mix is expected to be stable, since we combine the hardware-configuration phase with the task-allocation phase. For the required volume of products, we use integer programming to select the number of stations and the number of machines at each station and to allocate tasks to stations. We use queueing network analysis, which takes into account the mean and variance of processing times among different products to determine the necessary capacity of the material-handling system. We iterate between the two analyses to find the combined solution with the lowest costs. Work-in-process costs are also included in the analysis. Computational results are presented.     

PCB assembly scheduling with alternative nozzle types for one component type

The placement machine is the bottleneck of a printed circuit board (PCB) assembly line. The type of machine considered in this paper is the beam-type placement machine that can simultaneously pick up several components from feeders. It is assumed that the number of nozzle types (NTs) is less than the number of heads on the beam. The objective of the PCB assembly scheduling for a single placement machine is to minimize the cycle time based on the average machine operation time instead of the travelling distance. To minimize the cycle time, the number of turns and the number of pickups should be minimized. The PCB assembly scheduling is hierarchically decomposed into four problems: the nozzle assignment problem, the head allocation problem, the component type (CT) grouping problem and the pickup clustering problem, which are optimized successively and iteratively. First, the nozzle assignment problem considering alternative NTs for one CT is dealt with by the proposed genetic algorithm. For a given nozzle assignment solution, the head allocation problem is solved by a previously greedy heuristic to minimize the number of turns.Then, the CT grouping problem and the pickup clustering problem are solved by a proposed greedy heuristic and a modified agglomerative hierarchical clustering approach, respectively, to minimize the number of pickups. Numerical experiments are carried out to examine the performances of these proposed heuristic approaches. The importance of considering alternative NTs for one CT for the cycle time is also confirmed.     

On optimal delivery of combination therapy for tumors

A mathematical model for the scheduling of angiogenic inhibitors in combination with a chemotherapeutic agent is formulated. Conditions are given that allow tumor eradication under constant infusion therapies. Then the optimal scheduling of a vessel disruptive agent in combination with a cytotoxic drug is considered as an optimal control problem. Both theoretical and numerical results on the structure of optimal controls are presented.     

The Economic and Environmental Impact of Wastepaper Trade and Recycling in India

There have been increasing pressures by governments and nongovernmental organizations to restrict international trade in waste in the conviction that each nation has to take care of its own waste. We develop a sectoral flow model to investigate if free trade in nontoxic waste can support economic development and simultaneously reduce environmental degradation. The model is formulated as a nonlinear programming model with an objective function that minimizes environmental and economic costs. The model in principle describes the life cycle of Indian paper: Preliminary results suggest that trade in wastepaper is both economically and environmentally advantageous. The results also show that domestic and imported waste-paper are complementary and that import of wastepaper does not "crowd out" the domestic waste paper sector. This implies that the current trend of increasing trade of wastepaper does contribute to a more sustainable paper cycle in India.     

Construction of Selection Indexes with Restrictions

In this paper the problem of unistage selection with inequality constraints is formulated. If the predictor and criterion variables are all normally distributed, this problem can be written as a convex programming problem, with a linear objective function and with linear constraints and a quadratic constraint. Using the duality theory, for convex nonlinear programming it is proved, that its dual problem can be transformed into a convex minimization problem with non-negativity conditions. Good computational methods are known for solving this problem. By the help of the dual problem sufficient conditions for a solution of the original primal problem are derived and illustrated by an example of practical interest.     

Redesigning metabolic networks using mathematical programming

The design of new generation bioprocessing plants is increasingly dependent on the design of process-compatible microorganisms. The latter, whether through genetic or physiological manipulations, can be greatly assisted by metabolic engineering. An emerging powerful tool in metabolic engineering research is computer-assisted cell design using mathematical programming. In this work, the problem of optimizing cellular metabolic networks has been formulated as a Mixed Integer Nonlinear Programming (MINLP) model. The model can assist genetic engineers to identify which cellular enzymes should be modified, and the new levels of activity required to produce an optimal network. Results are presented from the tricarboxylic acid cycle in Dictyostelium discoideum. Copyright 1998 John Wiley & Sons, Inc.