Sevast'yanov's algorithm for the flow-shop scheduling problem

We consider the flow-shop scheduling problem. The objective is to schedule the jobs on the machines so that we minimize the time by which all jobs are completed. We studied and implemented different versions of the algorithm of Sevast'yanov based on linear programming to solve this problem. Using CPLEX, we did computational tests with random instances having up to 1000 jobs and 100 machines. If the size of the flow-shop scheduling problem is small or if the running time is not a critical factor, the Nawaz-Enscore-Ham approximation algorithm still performs better. But if the running time is an important factor, Sevast'yanov's algorithm can be a very good alternative especially in presence of very large scale instances with a relatively small number of machines.     

随机置换的分量与单调重新构组问题的计算等价性

In this note, it is shown that the monotone reconstruction problem is equi-valent to that of sorting, in the sense of computational complexity. In particular from any given sorting algorithm A, an algorithm B for the monotone reconstruc-tion problem can be developed with at most O(m) time and O( m) space cost more than that used in A, and vice versa. As a consequence of this result, it is obtai-ned that the time complexity of the monotone reconstruction problem of n-ele-ment random permutations is O(nlogn).     

A note on parallel-machine scheduling with deteriorating jobs

We consider a parallel-machine scheduling problem of minimizing the total completion time. The processing time of a job is a linear function of its starting time and deterioration rate. This problem is known to be NP-hard, even for the case with two machines. In this note, we generalize an existing lower bound for the two-machine case to the general case with an arbitrary number of machines. Despite the generalization concerning machine number, our bound has one extra term that makes our bound tighter than the existing one.     

A tabu search algorithm for the Open Shop problem

In this paper we consider the minimum makespan Open Shop problem without preemption. It is well-known that the case with only two machines can be optimally solved in linear time, whereas the problem with an arbitrary number of machines is NP-hard in the strong sense. We propose a tabu search algorithm for the solution of the problem which uses simple list scheduling algorithms to build the starting solutions. The algorithm is extensively tested on randomly generated instances.     

Meta-heuristic algorithms for wafer sorting scheduling problems

Wafer sorting is usually regarded as the most critical stage in the whole wafer probing process. This paper discusses the wafer sorting scheduling problem (WSSP) with total setup time minimization as the primary criterion and the minimization of the number of machines used as the secondary criterion. Although the need to consider multiple criteria in real-world WSSPs is widely recognized, the present study is the first attempt to investigate this argument with setups consideration. In view of the strongly NP-hard nature of this problem, three meta-heuristic algorithms—an ant colony system algorithm, a Genetic algorithm, and a Tabu search algorithm are proposed. The proposed meta-heuristics are empirically evaluated by 480 simulation instances based on the characteristics of a real wafer testing shop-floor and found to be very effective in terms of finding good quality solutions.     

Local search metaheuristics for discrete–continuous scheduling problems

Problems of scheduling nonpreemptable jobs which require simultaneously a machine from a set of parallel, identical machines and a continuous, renewable resource are considered. For each job there are known: its processing speed as a continuous, concave function of a continuous resource allotted at a time and its processing demand. The optimization criterion is the schedule length. The problem can be decomposed into two interrelated subproblems: (i) to sequence jobs on machines, and (ii) to find an optimal (continuous) resource allocation among jobs already sequenced. Problem (ii) can be formulated as a convex programming problem with linear constraints and solved using proper solvers. Thus, the problem remains to generate a set of all feasible sequences of jobs on machines (this guarantees finding an optimal schedule in the general case). However, the cardinality of this set grows exponentially with the number of jobs. Thus, we propose to use heuristic search methods defined on the space of feasible sequences. Three metaheuristics: tabu search (TS), simulated annealing (SA) and genetic algorithm (GA) have been implemented and compared computationally with a random sampling technique. The computational experiment has been carried out on an SGI PowerChallenge XL computer with 12 RISC R8000 processors. Some directions for further research have been pointed out.     

Auxiliary tool allocation in flexible manufacturing systems

This paper analyses a new approach to the machine loading problem arising in flexible manufacturing systems (FMSs). This approach allows the operations to be assigned to machines assuming that machines have access to all the tools required for their operations. This exploits the flexibility of the FMS completely. Next an allocation of tools to machines is determined which satisfies the tool requirements for each machine and minimizes the total number of tools. Thus this approach minimizes the unnecessary tool duplications in the system and maximizes the tool utilization. The problem is modeled as an integer linear program (ILP). We notice that the main problem has a block diagonal structure which is decomposable by relaxing a set of linking constraints. Each separated sub-problem represents a problem of allocation of a single type of tools. We develop a branch-and-bound based exact solution procedure and three heuristic procedures to solve the sub-problems. Our lower bounding approach uses Lanrangean relaxation. The solutions to the Lagrangean relaxation are further used to determine the branching sequences and to develop heuristic approaches. Since finding even a feasible solution to the main problem is NP-hard, we develop only enumerative procedures to solve the main problem. Finally, these solution procedures are tested on randomly generated test problems.     

Capacity planning for phased implementation of flexible manufacturing systems under budget restrictions

We consider a problem of gradually replacing conventional dedicated machines with flexible manufacturing modules (FMMs) under budget restrictions over a finite planning horizon assuming that dedicated machines cannot be purchased during the planning horizon and acquired FMMs are kept until the end of the horizon. In the problem, a replacement schedule is to be determined and operations are to be assigned to the FMMs or the dedicated machines with the objective of minimizing the sum of discounted costs of acquisition and operation of FMMs and operation costs of conventional dedicated machines. In this research, the problem is formulated as a mixed integer linear program and solved by a Lagrangean relaxation approach. A subgradient optimization method is employed to obtain lower bounds of solutions and a multiplier adjustment method is devised to improve the lower bounds. We develop a linear programming-based Lagrangean heuristic algorithm to find a good feasible solution of the original problem in a reasonable amount of computation time. The algorithm is tested on randomly generated test problems and the results are reported.     

Combined Hierarchies of Finite Random Access Machines

A finitary approach to the computational complexity theory is considered. Classes of finite random access machines are investigated. Combined space-and-time computational complexity hierarchies of predicates (properties, sets) recognizable by these machines are constructed. Bibliography: 2 titles.     

Two meta-heuristics for parallel machine scheduling with job splitting to minimize total tardiness

Parallel machine scheduling is a popular research area due to its wide range of potential application areas. This paper focuses on the problem of scheduling n independent jobs to be processed on m identical parallel machines with the aim of minimizing the total tardiness of the jobs considering a job splitting property. It is assumed that a job can be split into sub-jobs and these sub-jobs can be processed independently on parallel machines. We present a mathematical model for this problem. The problem of total tardiness on identical parallel machines is NP-hard. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using an optimization solver is extremely difficult. We propose two meta-heuristics: Tabu search and simulated annealing. Computational results are compared on random generated problems with different sizes.     

Stochastically minimizing total flowtime in flowshops with no waiting space

The problem of scheduling n jobs in a two-machine flowshop with constant and known processing times is considered with the total flowtime performance measure. The machines are subject to random breakdowns and there is no waiting space between them. The problem is formulated and an expression for the completion time of the jobs is obtained in terms of the processing times and the breakdown elements. Provided that the counting processes associated with both machines have stationary increments property, a sequence that stochastically minimizes the performance criterion is established for the cases when only the first or the second machine suffers breakdowns.     

Throughput-oriented channel assignment for opportunistic spectrum access networks

Cognitive radio (CR) is a revolutionary technology in wireless communications that enhances spectrum utilization by allowing opportunistic and dynamic spectrum access. One of the key challenges in this domain is how CR users cooperate to dynamically access the available spectrum opportunities in order to maximize the overall perceived throughput. In this paper, we consider the coordinated spectrum access problem in a multi-user single-transceiver CR network (CRN), where each CR user is equipped with only one half-duplex transceiver. We first formulate the dynamic spectrum access as a rate/power control and channel assignment optimization problem. Our objective is to maximize the sum-rate achieved by all contending CR users over all available spectrum opportunities under interference and hardware constraints. We first show that this problem can be formulated as a mixed integer nonlinear programming (MINLP) problem that is NP-hard, in general. By exploiting the fact that actual communication systems have a finite number of available channels, each with a given maximum transmission power, we transfer this MINLP into a binary linear programming problem (BLP). Due to its integrality nature, this BLP is expected to be NP-hard. However, we show that its constraint matrix satisfies the total unimodularity property, and hence our problem can be optimally solved in polynomial time using linear programming (LP). To execute the optimal assignment in a distributed manner, we then present a distributed CSMA/CA-based random access mechanism for CRNs. We compare the performance of our proposed mechanism with reference CSMA/CA channel access mechanisms designed for CRNs. Simulation results show that our proposed mechanism significantly improves the overall network throughput and preserves fairness.     

Flowshop scheduling problem to minimize total completion time with random and bounded processing times

The flowshop scheduling problems with n jobs processed on two or three machines, and with two jobs processed on k machines are addressed where jobs have random and bounded processing times. The probability distributions of random processing times are unknown, and only the lower and upper bounds of processing times are given before scheduling. In such cases, there may not exist a unique schedule that remains optimal for all feasible realizations of the processing times, and therefore, a set of schedules has to be considered which dominates all other schedules for the given criterion. We obtain sufficient conditions when transposition of two jobs minimizes total completion time for the cases of two and three machines. The geometrical approach is utilized for flowshop problem with two jobs and k machines.     

Greedy scheduling with custom-made objectives

We present a methodology to automatically generate an online job scheduling method for a custom-made objective and real workloads. The scheduling problem comprises independent parallel jobs and parallel identical machines and occurs in Massively Parallel Processing systems and computational Grids. The system administrator defines the scheduling objective that may consider job properties and priorities of users or user groups. Our scheduling method combines a Greedy scheduling algorithm with the dynamic sorting of the waiting queue. This sorting algorithm uses a criterion that is modifiable by a set of parameters. Finding good parameter settings for the sorting criterion is viewed as a nonlinear optimization problem which is solved with the help of Evolution Strategies. We evaluate our scheduling method with real workload data and compare it to approximated optimal offline solutions and to the online results of the standard EASY backfill algorithm.     

Arbitrary side observations in bandit problems

A bandit problem with side observations is an extension of the traditional two-armed bandit problem, in which the decision maker has access to side information before deciding which arm to pull. In this paper, essential properties of the side observations that allow achievability results with respect to optimal regret are extracted and formalized. The sufficient conditions for good side information obtained here admit various types of random processes as special cases, including i.i.d. sequences, Markov chains, deterministic periodic sequences, etc. A simple necessary condition for optimal regret is given, providing further insight into the nature of bandit problems with side observations. A game-theoretic approach simplifies the analysis and justifies the viewpoint that the side observation serves as an index specifying different sub-bandit machines.     

NP-hard cases in scheduling deteriorating jobs on dedicated machines

In this paper problems of time-dependent scheduling on dedicated machines are considered. The processing time of each job is described by a function which is dependent on the starting time of the job. The objective is to minimise the maximum completion time (makespan). We prove that under linear deterioration the two-machine flow shop problem is strongly NP-hard and the two-machine open shop problem is ordinarily NP-hard. We show that for the three-machine flow shop and simple linear deterioration there does not exist a polynomial-time approximation algorithm with the worst case ratio bounded by a constant, unless P=NP. We also prove that the three-machine open shop problem with simple linear deterioration is ordinarily NP-hard, even if the jobs have got equal deterioration rates on the third machine.     

A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem

We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig–Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time.     

Parallel-machine scheduling with simple linear deterioration to minimize total completion time

We consider the parallel-machine scheduling problem in which the processing time of a job is a simple linear increasing function of its starting time. The objective is to minimize the total completion time. We give a fully polynomial-time approximation scheme (FPTAS) for the case with m identical machines, where m is fixed. This study solves an open problem that has been posed in the literature for ten years.     

Optimal scheduling on parallel machines for a new order class

This paper addresses the problem of scheduling n unit length tasks on m identical machines under certain precedence constraints. The aim is to compute minimal length nonpreemptive schedules. We introduce a new order class which contains properly two rich families of precedence graphs: interval orders and a subclass of the class of series parallel orders. We present a linear time algorithm to find an optimal schedule for this new order class on any number of machines.     

Minimizing makespan and total completion time for parallel batch processing machines with non-identical job sizes

This paper considers the scheduling problem of parallel batch processing machines with non-identical job sizes. The jobs are processed in batches and the machines have the same capacity. The models of minimizing makespan and total completion time are given using mixed integer programming method and the computational complexity is analyzed. The bound on the number of feasible solutions is given and the properties of the optimal solutions are presented. Then a polynomial time algorithm is proposed and the worst case ratios for minimizing total completion time and makespan is proved to be 2 and (8/3–2/3 m) respectively. To test the proposed algorithm, we generate different levels of random instances. The computational results demonstrate the effectiveness of the algorithm for minimizing the two objectives.