for Journals by Title or ISSN for Articles by Keywords help
 Subjects -> COMPUTER SCIENCE (Total: 1991 journals)     - ANIMATION AND SIMULATION (27 journals)    - ARTIFICIAL INTELLIGENCE (76 journals)    - AUTOMATION (40 journals)    - COMPUTER ARCHITECTURE (9 journals)    - COMPUTER ASSISTED INSTRUCTION (25 journals)    - COMPUTER ENGINEERING (11 journals)    - COMPUTER GAMES (16 journals)    - COMPUTER GRAPHICS (32 journals)    - COMPUTER PROGRAMMING (19 journals)    - COMPUTER SCIENCE (1232 journals)    - COMPUTER SECURITY (44 journals)    - CYBERNETICS AND ROBOTICS (62 journals)    - DATA BASE MANAGEMENT (15 journals)    - DATA COMMUNICATIONS AND NETWORKS (75 journals)    - DATA MINING (23 journals)    - ELECTRONIC DATA PROCESSING (17 journals)    - INFORMATION SYSTEMS (93 journals)    - INTERNET (91 journals)    - SOCIAL WEB (46 journals)    - SOFTWARE (32 journals)    - THEORY OF COMPUTING (6 journals) COMPUTER SCIENCE (1232 journals)
 The end of the list has been reached or no journals were found for your choice.
 Journal of Scheduling   [SJR: 1.417]   [H-I: 38]   [2 followers]  Follow         Hybrid journal (It can contain Open Access articles)    ISSN (Print) 1099-1425 - ISSN (Online) 1094-6136    Published by Springer-Verlag  [2281 journals]
• Finding optimal tour schedules on transportation paths under extended time
window constraints
• Abstract: Abstract This paper addresses time-critical routing on a given path under release dates and deadline restrictions, while the minimization of the total weighted completion time is pursued. Since there may be destinations with flexible picking area resources that enable a delivery of goods before the defined release date at no additional costs, the well-known Line-Traveling Repairman problem (Line-TRPTW) is extended into the Line-TRPeTW. The Line-TRPeTW has various practical applications, such as, for example, the tour planning of an inland container ship along a river or that of a vehicle along a coastline. Although the feasibility variant of the Line-TRPTW/Line-TRPeTW is known to be strongly $${\mathcal {NP}}$$ -hard, a first practically applicable Branch&Bound procedure is generated. By making use of different dominance rules and lower bounds, a comprehensive computational study proves that instances comprising up to 200 requests and locations are solved to optimality in reasonable time. Moreover, the paper analyzes the complexity of the simpler variant with relaxed release dates at all customer locations. This relaxed variant provides tight lower bounds. Furthermore, the complexity analysis shows that the relaxed problem variant is binary $${\mathcal {NP}}$$ -hard even if deadlines are ignored, but can be efficiently solved by a specific Dynamic Programming approach that runs in pseudo-polynomial time.
PubDate: 2016-05-12

• Real-time management of berth allocation with stochastic arrival and
handling times
• Abstract: Abstract In this research we study the berth allocation problem (BAP) in real time as disruptions occur. In practice, the actual arrival times and handling times of the vessels deviate from their expected or estimated values, which can disrupt the original berthing plan and possibly make it infeasible. We consider a given baseline berthing schedule, and solve the BAP on a rolling planning horizon with the objective to minimize the total realized cost of the updated berthing schedule, as the actual arrival and handling time data is revealed in real time. The uncertainty in the data is modeled by making appropriate assumptions about the probability distributions of the uncertain parameters based on past data. We present an optimization-based recovery algorithm based on set partitioning and a smart greedy algorithm to reassign vessels in the event of disruption. Our research problem derives from the real-world issues faced by the Saqr port, Ras Al Khaimah, UAE, where the berthing plans are regularly disrupted owing to a high degree of uncertainty in information. A simulation study is carried out to assess the solution performance and efficiency of the proposed algorithms, in which the baseline schedule is the solution of the deterministic BAP without accounting for any uncertainty. Results indicate that the proposed reactive approaches can significantly reduce the total realized cost of berthing the vessels as compared to the ongoing practice at the port.
PubDate: 2016-04-23

• Unary NP-hardness of minimizing the number of tardy jobs with deadlines
• Abstract: Abstract For single machine scheduling to minimize the number of tardy jobs with deadlines, Lawler showed in 1983 that the problem is binary NP-hard. But the exact complexity (unary NP-hard or pseudo-polynomial-time solvability) is a long- standing open problem. We show in this paper that the problem is unary NP-hard. Our research also implies that the scheduling problem for finding an optimal schedule to minimize the number of tardy jobs that also satisfies the restriction of deadlines is unary NP-hard. As a consequence, some multi-agent scheduling problems related to minimizing the number of tardy jobs and maximum lateness are unary NP-hard.
PubDate: 2016-04-22

• An exact algorithm for parallel machine scheduling with conflicts
• Abstract: Abstract We consider an extension of classic parallel machine scheduling where a set of jobs is scheduled on identical parallel machines and an undirected conflict graph is part of the input. Each node in the graph represents a job, and an edge implies that its two jobs are conflicting, meaning that they cannot be scheduled on the same machine. The goal is to find an assignment of the jobs to the machines such that the maximum completion time (makespan) is minimized. We present an exact algorithm based on branch and price that combines methods from bin packing, scheduling, and graph coloring, with appropriate modifications. The algorithm has a good computational performance even for parallel machine scheduling without conflicting jobs.
PubDate: 2016-04-22

• Improved approaches to the exact solution of the machine covering problem
• Abstract: Abstract For the basic problem of scheduling a set of n independent jobs on a set of m identical parallel machines with the objective of maximizing the minimum machine completion time—also referred to as machine covering—we propose a new exact branch-and-bound algorithm. Its most distinctive components are a different symmetry-breaking solution representation, enhanced lower and upper bounds, and effective novel dominance criteria derived from structural patterns of optimal schedules. Results of a comprehensive computational study conducted on benchmark instances attest to the effectiveness of our approach, particularly for small ratios of n to m.
PubDate: 2016-04-22

• Scheduling with time-dependent discrepancy times
• Abstract: Abstract In time-dependent scheduling, various processing time functions are studied, yet absolute value functions have surprisingly been omitted from the discussion. Such a processing time function increases linearly with a job’s discrepancy from its ideal midtime. The objective is to find a schedule that minimizes the makespan, introducing the discrepancy time minimization problem. This single-machine scheduling problem with time-dependent processing times is motivated by optimization of walking times on a car assembly line. Its decision version is NP hard, as we show by reduction of the even–odd partition problem. For the variant with known start time, we develop several heuristics. Further insights form lower bounds and dominance rules for a branch-and-bound search. Numerical experiments show the performance of our algorithms on problem instances of up to 60 jobs. For the variant with common ideal midtime and flexible start time, we present a polynomial-time algorithm.
PubDate: 2016-04-15

• A parameterized complexity view on non-preemptively scheduling

• Abstract: Abstract We study the problem of non-preemptively scheduling n jobs, each job j with a release time  $$t_j$$ , a deadline  $$d_j$$ , and a processing time  $$p_j$$ , on m parallel identical machines. Cieliebak et al. (2004) considered the two constraints $$d_j-t_j \le \lambda {}p_j$$ and $$d_j-t_j \le p_j +\sigma$$ and showed the problem to be NP-hard for any  $$\lambda >1$$ and for any  $$\sigma \ge 2$$ . We complement their results by parameterized complexity studies: we show that, for any  $$\lambda >1$$ , the problem remains weakly NP-hard even for  $$m=2$$ and strongly W[1]-hard parameterized by m. We present a pseudo-polynomial-time algorithm for constant m and  $$\lambda$$ and a fixed-parameter tractability result for the parameter m combined with  $$\sigma$$ .
PubDate: 2016-04-08

• Preemptive scheduling on uniformly related machines: minimizing the sum of
the largest pair of job completion times
• Abstract: Abstract We revisit the classic problem of preemptive scheduling on m uniformly related machines. In this problem, jobs can be arbitrarily split into parts, under the constraint that every job is processed completely, and that the parts of a job are not assigned to run in parallel on different machines. We study a new objective which is motivated by fairness, where the goal is to minimize the sum of the two maximal job completion times. We design a polynomial time algorithm for computing an optimal solution. The algorithm can act on any set of machine speeds and any set of input jobs. The algorithm has several cases, many of which are very different from algorithms for makespan minimization (algorithms that minimize the maximum completion time of any job), and from algorithms that minimize the total completion time of all jobs.
PubDate: 2016-04-06

• Necessary and sufficient optimality conditions for scheduling unit time
jobs on identical parallel machines
• Abstract: Abstract In this paper we characterize optimal schedules for scheduling problems with parallel machines and unit processing times by providing necessary and sufficient conditions of optimality. We show that the optimality conditions for parallel machine scheduling are equivalent to detecting negative cycles in a specially defined graph. For a range of the objective functions, we give an insight into the underlying structure of the graph and specify the simplest types of cycles involved in the optimality conditions. Using our results we demonstrate that the optimality check can be performed by faster algorithms in comparison with existing approaches based on sufficient conditions.
PubDate: 2016-04-02

• A Step Counting Hill Climbing Algorithm applied to University Examination
Timetabling
• Abstract: Abstract This paper presents a new single-parameter local search heuristic named step counting hill climbing algorithm (SCHC). It is a very simple method in which the current cost serves as an acceptance bound for a number of consecutive steps. This is the only parameter in the method that should be set up by the user. Furthermore, the counting of steps can be organised in different ways; therefore, the proposed method can generate a large number of variants and also extensions. In this paper, we investigate the behaviour of the three basic variants of SCHC on the university exam timetabling problem. Our experiments demonstrate that the proposed method shares the main properties with the late acceptance hill climbing method, namely its convergence time is proportional to the value of its parameter and a non-linear rescaling of a problem does not affect its search performance. However, our new method has two additional advantages: a more flexible acceptance condition and better overall performance. In this study, we compare the new method with late acceptance hill climbing, simulated annealing and great deluge algorithm. The SCHC has shown the strongest performance on the most of our benchmark problems used.
PubDate: 2016-04-02

• Measuring the impact of adversarial errors on packet scheduling strategies
• Abstract: Abstract In this paper, we explore the problem of achieving efficient packet transmission over unreliable links with worst-case occurrence of errors. In such a setup, even an omniscient offline scheduling strategy cannot achieve stability of the packet queue, nor is it able to use up all the available bandwidth. Hence, an important first step is to identify an appropriate metric to measure the efficiency of scheduling strategies in such a setting. To this end, we propose an asymptotic throughput metric which corresponds to the long-term competitive ratio of the algorithm with respect to the optimal. We then explore the impact of the error detection mechanism and feedback delay on our measure. We compare instantaneous with deferred error feedback, which requires a faulty packet to be fully received in order to detect the error. We propose algorithms for worst-case adversarial and stochastic packet arrival models, and formally analyze their performance. The asymptotic throughput achieved by these algorithms is shown to be close to optimal by deriving lower bounds on the metric and almost matching upper bounds for any algorithm in the considered settings. Our collection of results demonstrate the potential of using instantaneous feedback to improve the performance of communication systems in adverse environments.
PubDate: 2016-04-01

• Optimal K -unit cycle scheduling of two-cluster tools with residency
constraints and general robot moving times
• Abstract: Abstract The semiconductor manufacturing industry is significantly expensive both in equipment and materials. Cluster tools, a type of automated manufacturing system integrating processing modules and transport modules, are commonly used in this industry. Nowadays, multi-cluster tools, which are composed of several cluster tools connected by joint buffer modules, are often used for wafer production. This paper deals with K-unit cycle scheduling problems in single-armed two-cluster tools for processing identical wafers in deterministic settings. In a K-unit cycle, K wafers are exactly inserted into the two-cluster tool, and K completed wafers leave the two-cluster tool, usually not the same K wafers. Residency constraints and general moving times by the robot are both considered. The objective is to obtain optimal K-unit cycle schedules, which minimize cycle times. To analyze this scheduling problem in detail, a mixed integer linear programming (MILP) model is formulated and solved. Numerical examples are used to explain how the solution can be obtained from the MILP model in a K-unit cycle.
PubDate: 2016-04-01

• Relocation scheduling subject to fixed processing sequences
• Abstract: Abstract This study addresses a relocation scheduling problem that corresponds to resource-constrained scheduling on two parallel dedicated machines where the processing sequences of jobs assigned to the machines are given and fixed. Subject to the resource constraints, the problem is to determine the starting times of all jobs for each of the six considered regular performance measures, namely, the makespan, total weighted completion time, maximum lateness, total weighted tardiness, weighted number of tardy jobs, and number of tardy jobs. By virtue of the proposed dynamic programming framework, the studied problem for the minimization of makespan, total weighted completion time, or maximum lateness can be solved in $$O(n_1n_2(n_1+n_2))$$ time, where $$n_1$$ and $$n_2$$ are the numbers of jobs on the two machines. The simplified case with a common job processing time can be solved in $$O(n_1n_2)$$ time. For the objective function of total weighted tardiness or weighted number of tardy jobs, this problem is proved to be NP-hard in the ordinary sense, and the case with a common job processing length is solvable in $$O(n_1n_2\min \{n_1,n_2\})$$ time. The studied problem for the minimization of number of tardy jobs is solvable in $$O(n^2_1n^2_2(n_1+n_2)^2)$$ time. The solvability of the common-processing-time problems can be generalized to the m-machine cases, where $$m\ge 3$$ .
PubDate: 2016-04-01

• An exact algorithm for an integrated project staffing problem with a
homogeneous workforce
• Abstract: Abstract When scheduling projects under resource constraints, assumptions are typically made with respect to the resource availability. In resource scheduling problems important assumptions are made with respect to the resource requirements. As projects are typically labour intensive, the underlying (personnel) resource scheduling problems tend to be complex due to different rules and regulations. In this paper, we aim to integrate these two interrelated scheduling problems to minimise the overall cost. For that purpose, we propose an exact algorithm for the project staffing with resource scheduling constraints. Detailed computational experiments are presented to evaluate different branching rules and pruning strategies and to compare the proposed procedure with other optimisation techniques.
PubDate: 2016-04-01

• Ant colony systems for the single-machine total weighted earliness
tardiness scheduling problem
• Abstract: Abstract Single-machine weighted earliness tardiness scheduling is a prevalent problem in just-in-time production environments. Yet, the case with distinct due dates is strongly NP-hard. Herein, it is approximately solved using ASV, an ant colony-based system with a reduced number of ants and of colonies and with daemon actions that explore the search space around the ants using a variable neighborhood search (VNS). The numerical investigation provides computational proof of the utility of the daemon actions. In addition, it infers that these latter can be applied either to the initial or to subsequent colonies. Furthermore, it highlights the importance of using ant colony optimization as the multiple restart engine of VNS. Finally, it shows that ASV obtains the optimum for most small-sized instances. It has a 0.2 % average deviation from the optimum over all benchmark instances.
PubDate: 2016-04-01

• A note on longest processing time algorithms for the two uniform parallel
machine makespan minimization problem
• Abstract: Abstract This note considers the longest processing time heuristic for scheduling n independent jobs on two uniform parallel machines to minimize the makespan. A posterior worst-case performance ratio, by depending on the index of the latest job inserted in the machine where the makespan takes place, is developed for this heuristic, and some examples demonstrate that the ratio is tight.
PubDate: 2016-04-01

• Single machine scheduling problems with uncertain parameters and the OWA
criterion
• Abstract: Abstract In this paper a class of single machine scheduling problems is discussed. It is assumed that job parameters, such as processing times, due dates, or weights are uncertain and their values are specified in the form of a discrete scenario set. The ordered weighted averaging (OWA) aggregation operator is used to choose an optimal schedule. The OWA operator generalizes traditional criteria used in decision making under uncertainty, such as the maximum, average, median, or Hurwicz criterion. It also allows us to extend the robust approach to scheduling by taking into account various attitudes of decision makers towards a risk. In this paper, a general framework for solving single machine scheduling problems with the OWA criterion is proposed and some positive and negative computational results for two basic single machine scheduling problems are provided.
PubDate: 2016-04-01

• Non-preemptive buffer management for latency sensitive packets
• Abstract: Abstract The delivery of latency sensitive packets is a crucial issue in real-time applications of communication networks. Such packets often have a firm deadline and a packet becomes useless if it arrives after its deadline. The deadline, however, applies only to the packet’s journey through the entire network; individual routers along the packet’s route face a more flexible deadline. We study policies for admitting latency sensitive packets at a router. Each packet is tagged with a value. A packet waiting at a router loses value over time as its probability of arriving at its destination on time decreases. The router is modeled as a non-preemptive queue, and its objective is to maximize the total value of the forwarded packets. When a router receives a packet, it must either accept it (and delay future packets), or reject it immediately. The best policy depends on the set of values that a packet can take. We consider three natural sets: an unrestricted model, a real-valued model, where any value over 1 is allowed, and an integral-valued model. For the unrestricted model, we prove that there is no constant competitive ratio algorithm. For the real-valued model, we give a randomized 4-competitive algorithm and a matching lower bound (up to low order terms). We also provide a deterministic lower bound of $$\phi ^3 - {\varepsilon }\approx 4.236$$ , almost matching the previously known 4.24-competitive algorithm. For the integral-valued model, we describe a deterministic 4-competitive algorithm, and prove that this is tight even for randomized algorithms (up to low order terms).
PubDate: 2016-03-17

• High-multiplicity scheduling on one machine with forbidden start and
completion times
• Abstract: Abstract We are interested in a single machine scheduling problem where jobs can neither start nor end on some specified instants, and the aim is to minimize the makespan. This problem models the situation where an additional resource, subject to unavailability constraints, is required to start and to finish a job. We consider in this paper the high-multiplicity version of the problem, when the input is given using a compact encoding. We present a polynomial time algorithm for large diversity instances (when the number of different processing times is greater than the number of forbidden instants). We also show that this problem is fixed-parameter tractable when the number of forbidden instants is fixed, regardless of jobs characteristics.
PubDate: 2016-03-17

• An integrated model for the transshipment yard scheduling problem
• Abstract: Abstract A hub-and-spoke railway system is an efficient way of handling freight transport by land. A modern rail–rail train yard consists of huge gantry cranes that move the containers between the trains. In this context, we consider a rail–rail transshipment yard scheduling problem (TYSP) where the containers arrive to the hub and need to be placed on a train that will deliver them to their destination. In the literature, the problem is decomposed hierarchically into five subproblems, which are solved separately. First, the trains have to be grouped into bundles in which they visit the yard. Next, the trains have to be assigned to tracks within these bundles, namely parking positions. Then the final positions for the containers on trains have to be determined. Next, the container moves that need to be performed are assigned to the cranes. Finally, these moves have to be sequenced for each crane for processing. In this paper, an integrated MILP model is proposed, which aims to solve the TYSP as a single optimization problem. The proposed formulation also enables us to define more robust and complex objective functions that include key characteristics from each of the above-mentioned subproblems. The strength of our proposed formulation is demonstrated via computational experiments using the data from the literature. Indeed, the results show that the TYSP can be solved without the use of decomposition techniques and more insight can be obtained from the same input data used to solve particular single decomposed subproblems.
PubDate: 2016-03-16

JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327