Nonstrict vector summation in multi-operation scheduling

Sevastianov, Sergey
November 1998
Annals of Operations Research;1998, Vol. 83 Issue 1-4, p179
Academic Journal
We consider several multi-operation scheduling problems with m machines and n jobs, including flow shop, open shop, assembly line, and a few special cases of job shop with the minimum makespan criterion. It is demonstrated that the problems in question can be efficiently solved by approximation algorithms with fairly good performance guarantee in the worst case. The algorithms constructed are based on a geometric technique called ‘nonstrict vector summation’. It consists of assigning an (m - l)-dimensional vector to each job and then finding an order in which these vectors should be summed so that all partial sums would lie within a given family of half-spaces (specified for a given scheduling problem). The partial sums are allowed sometimes lo go out of this or that half-space of the family, which explains the term ‘nonstrict’ in the title of the paper. For the open shop problem, this technique guarantees its polynomial-time solution, provided that the maximum machine load lmax (i.e., the maximum over all machines of the total processing time of operations of a machine) is large enough. In the case of three machines and lmax as large as at least 7 times the maximum processing time of an operation, we can find the optimal schedule in O(n log n) time.


Related Articles

  • Optimal scheduling of tasks when service is subject to disruption: the preempt-repeat case. Glazebrook, Kevin D. // Mathematical Methods of Operations Research;2005, Vol. 61 Issue 1, p147 

    It has long been recognised that situations in which some key resource or service is to be allocated among jobs or customers competing for it are often subject to a range of uncertainties. Key amongst these concern the reliability of service itself. When the service being delivered to a job is...


    The problem is to determine the best preliminary production schedule for a new multiproduct plant to raise inventories from zero to the initial levels assumed by whatever system of inventory control is to be used thereafter. It is assumed that a single bottleneck resource is required by all...

  • OPTIMAL m-STAGE PRODUCTION SCHEDULE. Bagga, P. C.; Chakravarti, N. K. // CORS Journal;Jul68, Vol. 6 Issue 2, p71 

    Smith and Dudek found a solution of the optimal production schedule problem involving n jobs and m machines. This paper presents an alternate simpler solution and an algorithm, which also generate other optimal sequences.

  • OPTIMUM TIME COMPRESSION IN PROJECT SCHEDULING. Lamberson, L. R.; Hocking, R. R. // Management Science;Jun70, Vol. 16 Issue 10, pB-597 

    An algorithm based on convex programming is developed for optimum time compression in network scheduling systems. The development allows for the activity time-cost trade-off functions to be any differentiable convex function. Decomposition theory is then applied to reduce the amount of...

  • Minimizing maximum absolute lateness and range of lateness under generalized due dates on a single machine. Tanaka, Keisuke; Vlach, Milan // Annals of Operations Research;1999, Vol. 86 Issue 1-4, p507 

    We investigate the problems of minimizing the maximum absolute lateness and range of lateness under generalized due dates on a single machine. In contrast to the traditional due date cases, we show that these problems are unary NP-hard. Furthermore, we present simple approximation algorithms for...

  • Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem. Panwalkar, S. S.; Smith, M. L.; Seidmann, A. // Operations Research;Mar/Apr82, Vol. 30 Issue 2, p391 

    We consider an n job, one machine scheduling problem in which all jobs have a common due date. The objective is to determine the optimal value of this due date and an optimal sequence to minimize a total penalty function. This penalty function is based on the due date value and on the earliness...

  • Batch scheduling with deadlines on parallel machines. Brucker, Peter; Kovalyov, Mikhail Y.; Shafransky, Yakov M.; Werner, Frank // Annals of Operations Research;1998, Vol. 83 Issue 1-4, p23 

    The problem of scheduling G groups of jobs on m parallel machines is considered. Each group consists of several identical jobs. We have to find splittings of groups into batches (i.e. sets of jobs to be processed contiguously) and to schedule the batches on the machines. It is possible for...

  • On the calculation of the stability radius of an optimal or an approximate schedule. Sotskov, Yuri N.; Wagelmans, Albert P. M.; Werner, Frank // Annals of Operations Research;1998, Vol. 83 Issue 1-4, p213 

    The main objective of this paper is to stimulate interest in stability analysis for scheduling problems. In spite of impressive theoretical results in sequencing and scheduling, up to now the implementation of scheduling algorithms with a rather deep mathematical background in production...

  • ALMOST NONPREEMPTIVE SCHEDULES. de Werra, D. // Annals of Operations Research;1990, Vol. 26 Issue 1-4, p243 

    Graph-theoretical models are described for solving preemptive and nonpreemptive scheduling problems with renewable resources. Conditions are obtained for nonpreemptive schedules to exist. These results may be applied for reducing the preemptions in the schedules obtained by the two-phase method...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics