Japan Advanced Institute of Science and Technology

Japan Advanced Institute of Science and Technology

JAIST Repository

https://dspace.jaist.ac.jp/

Title

Author(s)

Citation

Issue Date

Type

Text version

URL

Rights

Description

Computational Diculty

Scheduling and Circuit Complexity

by KeisukeTanaka

Scho ol of InformationScience

Japan Advanced Instituteof Scienceand Technology

DissertationDirector: Professor Milan Vlach

January14, 1997

The classication of problems according to their computational diculty requires estab-

lishingb othupperandlowerboundsonthe amountof computationalresourcesnecessary

tosolvethem. Inthisthesis,weareinvestigatingcomputationaldicultybystudyingthe

complexityof scheduling problemsand b ooleancircuits. Inparticular,weare focusingon

single machine scheduling problems with new typ es of due dates and release dates, and

negation-limited circuits,where the numb erof negations availableis restricted.

In 1986, Hall proposed a new typ e of due dates called generalized due dates. First,

we investigate the problems of minimizing the maximum absolute lateness and range of

lateness under generalized due dates. In contrast to the traditional due date cases, we

showthattheseproblemsareNP-hardinthestrongsense. Furthermore,wepresentsimple

approximation algorithms with non-trivial p erformance guarantee for these problems.

Second, we are concerned with scheduling with both traditional and generalized due

dates, and show that a polynomial time algorithm exists for the problem of minimizing

the maximum of maximum latenesses induced by traditional and generalized due dates.

In addition to scheduling involving generalized due dates, we also consider scheduling

with a new typ e of release dates which are related to the traditional release dates in a

similarwayasthe generalizeddue datestothetraditional ones. In 1992,Ishii,Tada,and

Masuda proposed another newtyp e of due datescalled fuzzy due dates. Weimprovethe

algorithms for basic scheduling problems withfuzzy due dates.

The diculty of a problem can be expressedas the numb er of gates in acircuit with

the minimumnumb erof gates,whichcomputestheproblem. Weconsiderthe complexity

ofnegation-limitedinverters,givinglowerb oundsaswellasnewupperboundsonthesize

anddepthoftheinverters. Thissuggestsimprovedupperboundsforslicefunctionsaswell

asatighterrelationshipb etweennegation-limitedandgeneralcircuitcomplexity. Wealso

show lower bounds for various symmetric functions. Finally, we establish relationships

between the numb er of negations availableand circuit sizes.

Key Words: computational complexity, single machine scheduling, due dates, release