On single-machine scheduling without intermediate delays

This paper introduces the non-idling machine constraint where no intermediate idle time between the operations processed by a machine is allowed. In its first part, the paper considers the non-idling single-machine scheduling problem. Complexity aspects are first discussed. The “Earliest Non-Idling” property is then introduced as a sufficient condition so that an algorithm solving the original problem also solves its non-idling variant. Moreover it is shown that preemptive problems do have that property. The critical times of an instance are then introduced and it is shown that when their number is polynomial, as for equal-length jobs, a polynomial algorithm solving the original problem has a polynomial variant solving its non-idling version.     

A new bounding mechanism for the CNC machine scheduling problems with controllable processing times

In this study, we determine the upper and lower bounds for the processing time of each job under controllable machining conditions. The proposed bounding scheme is used to find a set of discrete efficient points on the efficient frontier for a bi-criteria scheduling problem on a single CNC machine. We have two objectives; minimizing the manufacturing cost (comprised of machining and tooling costs) and minimizing makespan. The technological restrictions of the CNC machine along with the job specific parameters affect the machining conditions; such as cutting speed and feed rate, which in turn specify the processing times and tool lives. Since it is well known that scheduling problems are extremely sensitive to processing time data, system resources can be utilized much more efficiently by selecting processing times appropriately.     

Design,planning, scheduling,and control problems of flexible manufacturing systems

The design and use of flexible manufacturing systems (FMSs) involve some intricate operations research problems.FMS design problems include, for example, determining the appropriate number of machine tools of each type, the capacity of the material handling system, and the size of buffers.FMS planning problems include the determination of which parts should be simultaneously machined, the optimal partition of machine tools into groups, allocations of pallets and fixtures to part types, and the assignment of operations and associated cutting tools among the limited-capacity tool magazines of the machine tools.FMS scheduling problems include determining the optimal input sequence of parts and an optimal sequence at each machine tool given the current part mix.FMS control problems are those concerned with, for example, monitoring the system to be sure that requirements and due dates are being met and that unreliability problems are taken care of. This paper defines and describes these FMS problems in detail for OR/MS researchers to work on.     

Scheduling flexible machining and assembly systems

Most scheduling papers consider flexible machining and assembly systems as being independent. In this paper, a heuristic two-level scheduling algorithm for a system consisting of a machining and an assembly subsystem is developed. It is shown that the upper level problem is equivalent to the two machine flow shop problem. The algorithm at the lower level schedules jobs according to the established product and part priorities. Related issues, such as batching, due dates, process planning and alternative routes, are discussed. The algorithm and associated concepts are illustrated on a number of numerical examples.     

A market approach to decentralized control of a manufacturing cell

Based on a fictitious market model, a decentralized approach is presented for the workstation scheduling in a CNC workshop. A multi-agent framework is proposed, where job agents and resource agents act as buyers and sellers of resource in the virtual market. With cost and benefit calculation of these agent activities, which reflects the state of the production environment, various, and often conflicting goals and interests influencing the scheduling process in practice can be balanced through a unified instrument offered by the markets. The paper first introduces a heuristic procedure that makes scheduling reservations in a periodic manner. A multi-agent framework is then introduced, in which job agents and resource agents seek appropriate job–workstation matches through bidding in the construction of the above periodic “micro-schedules”. A pricing policy is proposed for the price-directed coordination of agent activities in this. Simulation results demonstrate the feasibility of the proposed approach and give some insights on the effects of some decision making parameters. Future work will be focused on the designing of some more sophisticated coordination mechanism and its deployment.     

Analytical solution for Van der Pol–Duffing oscillators

In this paper, the problem of single-well, double-well and double-hump Van der Pol–Duffing oscillator is studied. Governing equation is solved analytically using a new kind of analytic technique for nonlinear problems namely the “Homotopy Analysis Method” (HAM), for the first time. Present solution gives an expression which can be used in wide range of time for all domain of response. Comparisons of the obtained solutions with numerical results show that this method is effective and convenient for solving this problem. This method is a capable tool for solving this kind of nonlinear problems.     

An alternative framework to Lagrangian relaxation approach for job shop scheduling

A new Lagrangian relaxation (LR) approach is developed for job shop scheduling problems. In the approach, operation precedence constraints rather than machine capacity constraints are relaxed. The relaxed problem is decomposed into single or parallel machine scheduling subproblems. These subproblems, which are NP-complete in general, are approximately solved by using fast heuristic algorithms. The dual problem is solved by using a recently developed “surrogate subgradient method” that allows approximate optimization of the subproblems. Since the algorithms for subproblems do not depend on the time horizon of the scheduling problems and are very fast, our new LR approach is efficient, particularly for large problems with long time horizons. For these problems, the machine decomposition-based LR approach requires much less memory and computation time as compared to a part decomposition-based approach as demonstrated by numerical testing.     

带有机器维修和两车辆派送的单机排序问题

研究了带有机器维修和工件派送的单机排序问题,该问题可以被视为一个集成生产和出站配送的排序模型。不同体积的工件需要在带有一个维修区间的机器上加工,且加工不可中断,然后由固定容量的两辆同类车批次交付给单客户,目标函数是极小化最大完工时间,本文提出了2-近似算法,并证明了2是紧界。     

The difference in a problem of rations from the Rhind mathematical papyrus

In an ancient Egyptian problem of bread distribution from the Rhind mathematical papyrus (dated between 1794 and 1550 B.C.), a procedure of “false position” is used in the calculation of a series of five rations. The algorithm is only partially illustrated in the problem text, and last century's prevailing interpretations suggested a determination of the series by trial and error. The missing part of the computational procedure is reconstructed in this article as an application of the algorithm, exemplified in the preceding section of the papyrus, to calculate an unknown quantity by means of the method of “false position.”     

考虑碳排放的多机可持续调度问题

考虑多机器生产环境下,研究在加工空档期允许关闭机器的可持续调度问题。同时对工件的指派、工件的开始加工时刻和机器在空档期是否开关机进行决策,以最小化碳排放为目标建立数学规划模型。设计了禁忌搜索混合算法求解模型,首先通过一个企业案例验证了模型和算法的有效性,然后通过仿真算例分析了算法的效率。计算结果表明,可持续调度方式在机器调度层面为企业减少了大量的碳排放。     

Acquiring new use of multiplication through classroom teaching: an exploratory study

This article analyzes the process in which pupils acquire new uses of multiplication to measure area. Behaviors of five 4th-grade pupils in a series of lessons on areas were studied in depth by qualitative case-study methodology. Their use of multiplication changed as the lesson evolved, characterized conceptually as “using multiplication as a label,” “using it positively to approach problems which have not been solved before,” and “using it effectively to achieve the goal of measuring areas.” These three phases show the pupils’ understanding of multiplication in the context of measuring areas from a secondary accompaniment to a powerful tool of thinking. The phases observed and the students’ progress between the phases differs noticeably among the pupils. Factors that foster learners’ progress are investigated by comparing their behaviors.     

Constraint Propagation and Problem Decomposition: A Preprocessing Procedure for the Job Shop Problem

In recent years, constraint propagation techniques have been shown to be highly effective for solving difficult scheduling problems. In this paper, we present an algorithm which combines constraint propagation with a problem decomposition approach in order to simplify the solution of the job shop scheduling problem. This is mainly guided by the observation that constraint propagation is more effective for small problem instances. Roughly speaking, the algorithm consists of deducing operation sequences that are likely to occur in an optimal solution of the job shop scheduling problem (JSP).The algorithm for which the name edge-guessing procedure has been chosen – since with respect to the job shop scheduling problem (JSP) the deduction of machine sequences is mainly equivalent to orienting edges in a disjunctive graph – can be applied in a preprocessing step, reducing the solution space, thus speeding up the overall solution process. In spite of the heuristic nature of edge-guessing, it still leads to near-optimal solutions. If combined with a heuristic algorithm, we will demonstrate that given the same amount of computation time, the additional application of edge-guessing leads to better solutions. This has been tested on a set of well-known JSP benchmark problem instances.     

Multi-objective assembly permutation flow shop scheduling problem: a mathematical model and a meta-heuristic algorithm

This study is devoted to schedule a three-stage manufacturing system including machining, assembly and batch processing stages. The system is supposed to be capable of manufacturing a variation of products. At the first stage, the need for machining raw parts causes the manufacturer to deal with a flow shop scheduling problem. In the next stage, processed parts should be assembled together in order to form desired products. It is noteworthy that several operations are not allowed to be executed simultaneously on the same machine. Second stage should be considered as a single-assembly line or a single team of operators, and finally the manufacturing processing stage. The considered objectives are to minimize completion time of all products (makespan) and sum of the earliness and tardiness costs, simultaneously. First, the proposed scheduling problem is formulated into a mixed-integer mathematical model, and then owing to the NP-hardness of the concluded model a meta-heuristic approach is applied. A hybrid algorithm is modified to create a powerful method in searching the discrete solution space of this problem by taking advantage of superiorities of both Genetic Algorithm and Particle Swarm Optimization methods. Numerical experiments are designed to evaluate the performance of the proposed algorithm.     

Performance of scheduling algorithms for no-wait flowshops with parallel machines

We study the performance of scheduling algorithms for a manufacturing system, called the ‘no-wait flowshop’, which consists of a certain number of machine centers. Each center has one or more identical parallel machines. Each job is processed by at most one machine in each center. The problem of finding the minimum finish time schedule is considered here in a flowshop consisting of two machine centers. Heuristic algorithms are presented and are analyzed in the worst case performance context. For the case of two centers, one with a single machine and the other with m, two heuristics are presented with tight performance guarantees of 3 − (1/m) and 2. When both centers have m machines, a heuristic is presented with an upper bound performance guarantee of . It is also shown that this bound can be reduced to 2(1 + ε). For the flowshop with any number of machines in each center, we provide a heuristic algorithm with an upper bound performance guarantee that depends on the relative number of machines in the centers.     

Complexity of flow time minimization in a crossdock truck scheduling problem with asymmetric handover relations

We address a novel truck scheduling problem arising in crossdocking logistics, in which inbound trucks carry items (pallets) which must be sorted and loaded onto outbound trucks. We minimize the utilisation of the warehouse by focusing on the synchronisation between the different related trucks. The problem is to assign the trucks to the doors of the warehouse and sequence them, in order to minimize the total time spent in the system by the pallets. We discuss the complexity of the problem, showing that even with a single door the problem is NP-hard in general, and discuss some special cases.     

Exploiting structure in quantified formulas

We study the computational problem “find the value of the quantified formula obtained by quantifying the variables in a sum of terms.” The “sum” can be based on any commutative monoid, the “quantifiers” need only satisfy two simple conditions, and the variables can have any finite domain. This problem is a generalization of the problem “given a sum-of-products of terms, find the value of the sum” studied in [R.E. Stearns and H.B. Hunt III, SIAM J. Comput. 25 (1996) 448–476]. A data structure called a “structure tree” is defined which displays information about “subproblems” that can be solved independently during the process of evaluating the formula. Some formulas have “good” structure trees which enable certain generic algorithms to evaluate the formulas in significantly less time than by brute force evaluation. By “generic algorithm,” we mean an algorithm constructed from uninterpreted function symbols, quantifier symbols, and monoid operations. The algebraic nature of the model facilitates a formal treatment of “local reductions” based on the “local replacement” of terms. Such local reductions “preserve formula structure” in the sense that structure trees with nice properties transform into structure trees with similar properties. These local reductions can also be used to transform hierarchical specified problems with useful structure into hierarchically specified problems having similar structure.     

Scheduling the truckload operations in automatic warehouses

This work presents a scheduling problem that arises in an automatic storage/retrieval warehouse system AS/RS involving the scheduling of the truck load operations. The truck loading operations are modelled as job shop problem with recirculation. The loads are considered as jobs, the pallets of a load are seen as the job’s operations. The forklifts are the machines. The minimization of the makespan allows minimizing the idle time of the warehouse’s equipments.     

Loading Multiple Pallets

This paper addresses the problem of loading pallets with non-identical items, i.e. what has been called the ‘Distributor's Pallet Packing Problem’. It concentrates on the situation where the consignment to be loaded cannot be accommodated on a single pallet. A greedy procedure for tackling this problem, which is based on a published approach for loading single pallets, is described and evaluated. Also discussed is a series of possible modifications of the basic method, whereby the pallets involved are packed simultaneously. A detailed performance analysis is undertaken. The paper concludes with suggestions for further work in this area.     

Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

The Enumeration of Permutations with a Prescribed Number of “Forbidden” Patterns

We initiate a general approach for the fast enumeration of permutations with a prescribed number of occurrences of “forbidden” patterns that seems to indicate that the enumerating sequence is always P-recursive. We illustrate the method completely in terms of the patterns “abc,” “cab,” and “abcd.”